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.
Sorun, diziyi kesişmeyen alt bölümlere (bir dizi ardışık öğe) en uygun şekilde bölmenin (veya uygun bölmelerin sayısını saymanın) gerekli olduğu gerçeğine indirgenirse, o zaman çözmeye değer. dinamik programlama kullanarak.
Örnek bir çözüm şeması aşağıdaki gibidir:
dp[i] - ilk i öğeleri için yanıt
dp[i] sayımı: sadece ilk i elemanlarını dikkate aldığımız için, i-inci eleman sonuncusu olacaktır, bu da bu elemanın son alt parçada ve aynı zamanda orada en sağda olacağı anlamına gelir. Bu nedenle, son alt parçanın (j) sol sınırı üzerinde yineleme yapabiliriz. Numaralandırma sürecinde, bu alt segmentin değerini hesaplayacağız ve eğer doğruysa, o zaman dp[i] ila dp[j - 1] ve alt segmentin değerini [j;i] yeniden hesaplayacağız.
Aşağıdaki basit problemi göz önünde bulundurun: bir tamsayı dizisi verildiğinde, onu kesişmeyen minimum sayıda alt parçaya bölmeniz gerekir, böylece her sayı bir alt parçaya dahil edilir ve her alt bölüm aynı sayıları içerir. Örneğin, bir 1 2 2 3 3 3 2 1 1 dizisi için en uygun bölüm şöyle görünür: [1] [2 2] [3 3 3] [2] [1 1]. Bu görev, basitçe diziden geçerek kolayca çözülebilir (tüm aynı ardışık öğeleri bir alt parçaya koyarız), ancak bir örnek için dinamik programlamayı kullanarak çözeceğiz.
int;
cin>> N;
// diziyi 1 dizinle doldur
vektör dizi(n + 1);
için (int i = 1; i <= n; i++)
cin>> dizi[i];
// başlangıçta +oo'yu dp değerlerine ayarla
vektör dp(n + 1, 1000000000);
// sıfır uzunluğundaki bir dizinin bölünmesi gerekmez, yani cevabı 0'dır
dp[0] = 0;
// artan i'de dp[i] için cevabı say
for (int ben = 1; i <= n; i++) {
// şu anda arr[i] son eleman, yani son alt segmentte en sağdaki sayı olacak
// bu son alt parçanın başladığı yerdeki tüm seçenekler arasında dolaş
for (int j = i; j > 0; j--) {
if (dizi[j] != dizi[i]) {
// bir öncekine eşit olmayan bir elemanla karşılaşırsanız, o zaman alt segment farklı sayılar içerecektir ve bu koşula uymuyor
// devam etmenin bir anlamı yok, çünkü sol kenarlığı sola kaydırmak, bu öğe kaybolmaz, bu yüzden kırarız
kırmak;
}
// son alt parçanın [j;i] olduğunu hayal edin
// bu yüzden ilk j-1 öğelerinin en uygun bölümünü almanız ve 1 eklemeniz gerekir ([j; i] alt bölümünün kendisi)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout
Öğeler herhangi bir alt segmente ait olmayabilirse, dp[i] = dp[i - 1] gibi uygun seçeneği düşünmeniz yeterlidir.
|
Diziyi tam olarak k alt parçaya bölmek gerekirse, dinamik programlamada ikinci parametre basitçe eklenir - kaç parçaya bölünecek.
Yani, şimdi aşağıdaki dp'yi ele alacağız:
dp[i][j], onları tam olarak j parçaya ayırırsak, ilk i öğelerinin yanıtıdır.
Geçersiz durumlara dikkat edin.
Dinamiklerin yeniden hesaplanması aynıdır, ancak ikinci parametre dikkate alınır. Yani, dp[i][k]'yi sayarak ve son j alt bölümünün sol kenarlığını sıralayarak, dp[i][k]'yi dp[j - 1][k - 1]'e ve parçanın değerini yeniden hesaplarız [j;i].
|
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.
|