Dinamik Programlamada Kalıplar - 2

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.

Bir problem sizden bir diziyi en iyi şekilde yok etmenizi/daraltmanızı/birleştirmenizi (veya benzerini) isterse, alt bölümlerde dinamik programlamayı kullanarak çözmeye çalışmalısınız.

dp[l][r]'yi bulalım - l'den r'ye indisleri olan bir alt segment için en uygun cevap. Dinamiklerin yeniden hesaplanması büyük ölçüde göreve bağlıdır, ancak aşağıdaki genel fikirler vardır:

1) l ve r uç elemanlarına bakın. Başka bir şekilde eşleşir veya tamamlarlarsa, dp[l][r] değerini dp[l+1][r-1] yoluyla güncellemek büyük olasılıkla mümkün olacaktır. Aksi takdirde dp[l][r-1] veya dp[l+1[r].
aracılığıyla
2) [l;r] segmentinin tek bir yapıyla temsil edilemediği sıklıkla olur. Daha sonra, bu alt parçanın tüm olası bölümlerini iki kısma ayırmak gerekir, yani l'den r-1'e kadar k elemanı üzerinde yineleme yapmak ve dp[l][r]'den dp[l][k] ve dp['ye kadar yeniden hesaplamak gerekir. k+1][r]. Daha küçük alt bölümlerde, bu bölümler de tasnif edildi, bu nedenle [l;r] alt bölümünü yalnızca iki parçaya değil, herhangi bir sayıda bölmeye ayırma seçenekleri dikkate alınır.
 

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.

Bir problemde bir permütasyonun varlığını kontrol etmeniz veya eşleşen permütasyonların sayısını veya benzer bir şeyi bulmanız gerekiyorsa, dinamik altküme programlamayı kullanmayı düşünmelisiniz.

Ana parametre, hangi öğelerin permütasyona dahil edildiğini ve hangilerinin edilmediğini gösteren bir bit maskesi olacaktır. Ayrıca, en son hangi öğenin dahil edildiğini gösteren ikinci bir parametre de sıklıkla gereklidir.

Genellikle permütasyonlar, grafiklerdeki yollar bağlamında görülebilir. Buna göre, klasik bir örnek olan Hamilton yol problemini ele alalım.
Bir Hamilton yolu, grafiğin her köşesinden tam olarak bir kez geçen basit bir yoldur. Basitçe, n'nin köşe sayısı olduğu n uzunluğunun bir permütasyonu olarak temsil edilebilir. Bu permütasyon içindeki sıra, bu yoldaki köşelerin geçildiği sırayı gösterecektir.

Grafikte bir Hamilton yolunun varlığını kontrol etmek için dp[mask][son] dinamiklerini başlatalım - maske bit maskesinde birlerle işaretlenmiş köşeleri atlayan ve son köşede sona eren basit bir yol var mı?
İlk değerler dp[2ⁱ][i] = true, geri kalanı false olacaktır, bu da her zaman köşelerden herhangi birinde başlayan boş bir yol olduğu anlamına gelir.
dp[mask][last] içinde true değerine sahip olmak, "yolu genişletmek" anlamında ileriye doğru geçişler yapacağız. Yani, maskede sıfır ile işaretlenmiş köşelerin sayısını arayacağız (yolda henüz ziyaret etmedik) ve aynı zamanda sondan bu köşeye bir kenar olacak şekilde (yol olmalıdır) mevcut bir kenar tarafından uzatılabilir). Yani dp[mask | 2^k][k] = true if dp[mask][last] = true AND mask & 2^k = 0 (k köşesi henüz ziyaret edilmedi) Ve sonunda bir kenar var -> k.
Nihayetinde, hepsi-birler bit maskesinin parametreleri ve herhangi bir son tepe noktası için dp'de gerçek bir değer varsa, bir Hamilton yolu vardır.