Climbing Stairs
n basamaklı bir merdiven var. Her adımda 1 veya 2 basamak çıkabilirsin. Kaç farklı yol var? Temel DP: dp[i] = dp[i-1] + dp[i-2] (Fibonacci).
Coin Change
Verilen coin listesi ile amount kadar para üret. En az kaç coin gerekir? Olası değilse -1. Unbounded knapsack.
0/1 Knapsack
Her item'ın weight ve value'su var. Kapasite W. Maksimum value elde et (her item en fazla 1 kez).
Longest Common Subsequence
İki string'in en uzun ortak alt dizisinin uzunluğu. LCS — klasik 2D DP. Örnek: 'abcde' vs 'ace' → 3 ('ace'). 'abc' vs 'abc' → 3. Formül: dp[i][j] = dp[i-1][j-1] + 1 (eşitse), max(dp[i-1][j], dp[i][j-1]).
Longest Increasing Subsequence
Bir dizide en uzun kesin artan altdizinin uzunluğu. LIS — O(n log n) patience sorting ile optimal.
Maximum Subarray (Kadane)
Bir dizide en büyük toplam alt diziyi bul. Kadane's algorithm: O(n) — şu ana kadarki max'i tut. Örnek: [-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1]). Tüm elemanlar negatifse en büyük (en az negatif) elemanı döndür.
Word Break
String s, wordDict'teki kelimelerle oluşturulabilir mi? Her kelime en az 1 kez, sırasıyla.
Edit Distance
word1'i word2'ye çevirmek için minimum işlem. İşlemler: insert, delete, replace (her biri 1).
Unique Paths
m×n grid'de (0,0)'dan (m-1,n-1)'e sadece sağ/aşağı. Kaç farklı yol var? Örnek: 3×7 grid → 28 yol. Formül: C(m+n-2, m-1). DP: dp[i][j] = dp[i-1][j] + dp[i][j-1].
House Robber
Bir dizi ev var. Yan yana iki ev soyamazsın (alarm bağlı). Maksimum para. Maks 2 durum: soy (i) veya soyma (i-1). Formül: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Örnek: [2,7,9,3,1] → 12 (ev 0, 2, 4 veya ev 1, 3).
Decode Ways
Sayı string'ini decode et. A=1, B=2, ..., Z=26. Kaç farklı decode yolu var? Örnek: '12' → 2 ('AB' veya 'L'). '226' → 3. '06' → 0 (leading zero). DP: dp[i] = dp[i-1] (1 harf) + dp[i-2] (2 harf, 10-26 arası).
Partition Equal Subset Sum
Dizi iki alt kümeye bölünebilir mi, eşit toplam? Subset sum problem. Toplam tek ise False. Örnek: [1,5,11,5] → True ([1,5,5] ve [11]). [1,2,3,5] → False. DP yaklaşımı: hedef = sum/2, set ile olası toplamları tut.
Longest Palindromic Subsequence
Bir string'in en uzun palindromik alt-dizisinin (subsequence) uzunluğunu bul. Karakterler arası karakter atlanabilir, sıra korunmalı. Örnek: 'bbbab' → 4 ('bbbb').
Longest Palindromic Substring
Bir string içindeki en uzun palindromik alt-string'i (substring) bul. Örnek: 'babad' → 'bab' (veya 'aba', uzunluk 3).
Matrix Chain Multiplication
Bir matris zincirinin çarpımı için minimum skaler çarpma sayısını bul. Matrisler soldan sağa çarpılır. Örnek: p = [1, 2, 3, 4] (3 matris: 1x2, 2x3, 3x4) → 18.
Minimum Path Sum
Sol-üst köşeden sağ-alt köşeye, sadece sağa/aşağı hareketle minimum toplam yol bul. Örnek: [[1,3,1],[1,5,1],[4,2,1]] → 7 (1→3→1→1→1).
Distinct Subsequences
String s, string t'nin kaç farklı alt-dizisini (subsequence) içeriyor? Örnek: s='rabbbit', t='rabbit' → 3.
Interleaving String
s3, s1 ve s2'nin bir interleaving'i mi? Karakter sırası korunmalı. Örnek: s1='aabcc', s2='dbbca', s3='aadbbcbcac' → True.
Burst Balloons
n balon, her patlatmada balonun sol ve sağındaki komşu balonların sayıları çarpılır. Tüm balonları patlatarak maksimum toplam puanı bul. Örnek: [3,1,5,8] → 167.
Regular Expression Matching
String s, pattern p ile eşleşiyor mu? '.' herhangi bir karakter, '*' önceki karakterin 0 veya daha fazlası. Örnek: s='aab', p='c*a*b' → True.
Target Sum
Her sayının önüne + veya - koyarak hedef toplama ulaş. Kaç farklı yol var? Örnek: nums=[1,1,1,1,1], target=3 → 5 yol.
Longest Common Substring
İki string arasındaki en uzun ortak alt-string'in (substring) uzunluğunu bul. Subsequence değil, SUBSTRING (bitişik olmalı). Örnek: s1='abcdef', s2='zbcdf' → 3 ('bcd').
Dinamik Programlama Nedir?
Dinamik programlama (DP), karmaşık problemleri daha küçük, örtüşen alt problemlere ayırarak çözen bir algoritma tekniğidir. Her alt problem yalnızca bir kez çözülür ve sonucu bir yerde saklanır (cache / memoization), böylece aynı alt problem tekrar hesaplanmaz. Bu yaklaşım, üssel zaman karmaşıklığına sahip problemleri polinom zamana indirgeyebilir.
Python'da dinamik programlama iki temel yaklaşımla uygulanır:
- Memoization (top-down): Rekürsif çözüm, sonuçları bir sözlükte (dict) saklar. Aynı alt problem tekrar geldiğinde sözlükten döner.
@lru_cachedecorator'ı ile tek satırda uygulanabilir. - Tabulation (bottom-up): Yinelemeli (iterative) çözüm, küçük alt problemlerden büyüğe doğru bir tablo doldurur. Genellikle bellek açısından daha verimlidir.
Klasik dinamik programlama problemleri arasında Fibonacci, 0/1 Knapsack,Coin Change, Edit Distance, Longest Common Subsequence (LCS) veLongest Increasing Subsequence (LIS) sayılabilir. Mülakatlarda en sık sorulan DP sorularından birkaçını yukarıda interaktif olarak çözebilirsin.
İlgili Kategoriler
Python Algoritma Soruları
Sıralama, arama, DP, graf ve string algoritmaları için 26+ interaktif soru.
Tüm Mülakat Kategorileri
Python mülakat soruları kataloğu: OOP, SQLite, Pandas, veri yapıları.
Python Kodları
Hazır Python kodu örnekleri: liste, dict, OOP, Pandas, Algoritmalar.