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.