Üstel zamanda patlayan kaba kuvveti, alt problemleri hatırlayarak milisaniyelere indirme disiplini.Alt problemi tanımla, geçişi yaz, tabloyu doldur: DP'yi ezber değil yöntem olarak öğrenin.
Bu Eğitimde ve Mühendislik Yolculuğunda Neden Gerekli?
01 • EĞİTİMDEKİ YERİ
Bu Eğitimde Neden Atlanmamalı?
Dinamik Programlama (DP), yazılımcıların %80'inin gözünde 'sihirli bir formül bulma' sanatı sanıldığı için en çok korkulan konudur. Oysa Modül 4'te özyineleme yazmayı ve Modül 1'de sözlükte veri saklamayı öğrendiysen DP'nin yarısını zaten biliyorsun: **DP = Özyineleme + Daha Önce Hesapladığını Hatırlama**. Bu modül, o korku duvarını yıkıp DP'yi mekanik bir 3 adım sistemine dönüştürmek için burada.
02 • KARİYER & ÜRETİM GERÇEĞİ
Mülakat Masasında ve Gerçek İş Hayatında Neden Lazım?
`git diff` algoritması (LCS / Edit Distance), doğal dil yazım düzeltme, finansal portföy/bütçe tahsisi (Knapsack) ve derleyici optimizasyonları doğrudan DP üzerinde çalışır. Üst düzey şirketlerin mülakatlarında bir DP sorusunu sakince durum-geçiş (state-transition) olarak açıklayabilmek seni aday havuzunun en üst %10'una taşır.
Kilidini AçarBu modülde kazanacağın refleks doğrudan şu aşamaları besler: Modül 7 (Greedy vs DP Ayrımı) ve Modül 8 (Memoized Arama Ağaçları)
Koda Başlamadan Önce Zihniyet Notu
Sakın doğrudan 2 boyutlu `dp[i][j]` tablosu çizerek başlamaya çalışma! Önce 'Şu an elimde hangi seçenekler var?' diyerek basit özyinelemeli karar ağacını düşün, sonra değişen parametreleri önbelleğe (memoization) al, en son tabloya çevir. İlk 5 soruda yavaş ilerlemen çok normal; beynin yeni bir düşünme kası inşa ediyor.
Modüle Hazırlık: Sorulara Nasıl Yaklaşmalısın?
1. `dp[i]` Tanımını Türkçe Tam Cümle Olarak Yaz
'dp[i], i. indekse kadar olan maksimum kazançtır' veya 'i. indekste BİTEN en uzun alt dizidir' ayrımını net yazmadan formül kurma.
2. Son Adımdaki Karara Odaklan
Tüm geçmişi aynı anda çözmeye çalışma; sadece son adımda 'bu elemanı aldım mı, almadım mı?' gibi son kararı önceki alt problemlere bağla.
3. Bellek Optimizasyonunu En Sona Bırak
Önce çalışan ve anlaşılır `dp` dizisini/matrisini kur; ancak doğruladıktan sonra sadece son iki satıra ihtiyaç duyulduğunu gösterip belleği daralt.
Adayların En Sık Düştüğü Tuzak: Sırt çantası (Knapsack / Coin Change) sorularında elemanları tek sefer mi yoksa sınırsız kez mi kullanabildiğine göre iç-dış döngü yönünü karıştırmak en yaygın hatadır.
Bu Modülün Teknik Kapsamı
Dinamik programlama, adayların en çok çekindiği ama doğru yöntemle en hızlı ilerleme kaydedilen konudur. Bu modül; durum (state) tanımı, geçiş (transition) formülü ve temel durumlar üzerinden sistematik bir DP yaklaşımı kazandırır.
Merdiven tırmanma gibi 1D problemlerden başlayıp matris yolları, en uzun ortak alt dizi, düzenleme mesafesi ve balon patlatma gibi aralık DP problemlerine ilerlersiniz.
Kimler İçin İdeal?
DP sorularını görünce ne yapacağını bilemeyen adaylar
Memoization ile tabulation arasındaki farkı netleştirmek isteyenler
Mid-level ve üzeri pozisyonlar için onsite mülakata hazırlananlar
Rekabetçi programlamaya giriş yapmak isteyen öğrenciler
Başlamadan Önce Cebinde Olması Gerekenler
Özyineleme ve temel durum (base case) kavramı (Modül 4)
İki boyutlu liste (matris) kullanımı
Big-O ile zaman/bellek analizi
Bu Modülü Bitirdiğinde Kazanacağın Refleksler
Bir problemi alt problemlere ayırıp DP durumunu tanımlamak
0/1 knapsack ve madeni para bozdurma kalıplarını tanımak
İki metin üzerinde 2D DP (LCS, edit distance) kurgulamak
Aralık DP ile 'son patlayan balon' tipi zor problemleri modellemek
Teknik Cephanelik ve Mülakatçı Beklentisi
Memoization
Tabulation
1D DP
2D DP
Knapsack
LIS
LCS
Edit Distance
Aralık DP
Kadane
DP soruları, adayın problemi yapılandırma ve adım adım optimize etme becerisini gösterir. Mülakatçı genellikle önce kaba kuvvet özyinelemeyi, sonra memoization'ı, ardından bellek optimizasyonunu ister.
Kademeli Antrenman Soruları (20 Soru)
Aşama 1: Isınma & Temel Refleks (Kolay) (7)
Kalıbı saf haliyle tanı ve elini ısıt (~15–20 dk / soru)
Her soruda üç şeyi açıkça yazmak: dp[i] neyi temsil ediyor, dp[i] önceki değerlerden nasıl hesaplanıyor ve temel durumlar neler. Modüldeki sorular bu sırayla zorlaşacak şekilde dizilmiştir.
Memoization mı tabulation mı tercih etmeliyim?
Mülakatta ikisi de kabul görür. Memoization düşünmesi daha kolaydır; tabulation ise özyineleme derinliği sınırına takılmaz ve bellek optimizasyonuna daha uygundur.
Bu modül hangi seviyede?
Kolay sorular girişe uygundur; Zor sorular (düzenleme mesafesi, balon patlatma) senior mülakatlarda karşılaşılan seviyededir.