Blog

Dynamic Programming 2: Edit Distance, LCS ve Knapsack ile Gerçek Problemler

İki boyutlu DP tabloları iki string'in ya da bir bütçenin prefix'lerini tutar: Levenshtein ile "Bunu mu demek istediniz?", LCS ile git diff'le aynı çıktıyı veren bir diff, 0/1 knapsack ile bütçe sınırlı kampanya seçimi. C# ile üçünü yazıyor, eşikli Levenshtein'ın 20 kat hızlandığını ölçüyor, tek satırlık knapsack'te döngü yönü tuzağını gösteriyor ve seriyi bir pattern karar tablosuyla kapatıyoruz.