Sorumluluk Reddi: Aşağıda açıklanan yöntem evrensel değildir ancak genellikle bir sorunu çözebilir veya doğru çözüme ulaşmanıza yardımcı olabilir.
Bazı eksenlerde (genellikle zaman ekseni veya bazı dizilerin indeksleri) bir dizi boşluk varsa ve seçilen boşlukların kesişmemesi için bunlardan bazılarını en uygun şekilde seçmeniz gerekiyorsa, o zaman dinamik programlama kullanmayı denemelisiniz. .
Yaklaşık çözüm şeması:
Başlangıçta, mevcut boşlukları sağ kenarlığa göre sıralarız. Şu dinamikleri başlatalım: dp[i] - ilk i aralığının cevabı.
Şu şekilde yeniden hesaplayacağız: önce bu aralığın kullanılmayacak durumunu ele alalım, sonra sadece dp[i] = dp[i-1]. Bunun i büyüdükçe dp[i] değerlerinin düşmemesini sağladığına dikkat edin. Ve bu mantıklı, çünkü. yeni bir boşluk ekleyerek küresel yanıtı kötüleştiremeyiz: ya yeni boşluğu görmezden geliriz ya da onu kullanarak daha karlı bir değişken oluştururuz. Şimdi, i'inci boşluğu kullanmak istiyorsak, sağ kenarları mevcut aralığın sol sınırından daha az olan boşlukları kullanabiliriz, çünkü bir dizi örtüşmeyen boşluk seçmemiz gerekir. Bunu yapmak için başlangıçta boşlukları sağ kenarlığa göre sıraladık, böylece şimdi gerekli konumu verimli bir şekilde bulabiliriz. Bu, mümkünse analitik olarak yapılabilir, ancak genel durumda, sağ sınırı geçerli olanın sol sınırından daha az olan ve aynı zamanda mümkün olan maksimum sınır olan bir binsearch ile bir boşluk bulmak mümkündür. bir. Açgözlü nedenlerle sağ sınırı maksimize etmek istiyoruz, çünkü büyüdükçe, cevap sadece artabilir. Buna göre gerekli p konumunu buluyoruz ve dp[i]'den dp[p]'ye ve i'inci aralığı yeniden hesaplıyoruz.