Blog
Mert Özen'in yazılım geliştirme, backend, frontend ve DevOps üzerine blog yazıları.
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.
Dynamic Programming 1: Memoization, Tabulation ve Alt Problemleri Tanımak
Dynamic programming, tekrar eden alt problemleri bir kez çözüp saklayarak exponential bir hesabı polinom zamana indirir: naive Fibonacci F(40) için 331 milyon çağrı yapar, memoization 79. C# ile memoization, tabulation ve O(1) bellek versiyonlarını ölçüyor, beş adımlı tarifle climbing stairs, house robber ve coin change'i çözüyor, yanlış memo key'ini ve stack overflow'u gerçek çıktıyla gösteriyoruz.