Dinamik programlama nedir? Merdiven çıkma problemi üzerinden açıklayın.

Dinamik programlama (DP), bir problemi örtüşen alt problemlere bölüp her alt problemi bir kez çözerek sonucunu saklama tekniğidir. İki şart aranır:

• Örtüşen alt problemler: aynı hesaplama tekrar tekrar yapılıyor.
• Optimal alt yapı: büyük problemin cevabı küçüklerin cevaplarından kurulabiliyor.

Problem

n basamaklı merdivende her seferinde 1 veya 2 basamak çıkabiliyorsunuz. Kaç farklı yolla tepeye ulaşırsınız?

Son adım ya 1 ya 2 basamaktır, dolayısıyla: f(n) = f(n-1) + f(n-2), f(1)=1, f(2)=2. (Fibonacci ile aynı yapı.)

# Naif özyineleme: O(2^n), aynı değerler defalarca hesaplanır
def climb(n):
    if n <= 2: return n
    return climb(n - 1) + climb(n - 2)

# 1) Top-down: memoization -> O(n) zaman, O(n) bellek
from functools import lru_cache
@lru_cache(maxsize=None)
def climb_memo(n):
    if n <= 2: return n
    return climb_memo(n - 1) + climb_memo(n - 2)

# 2) Bottom-up: tabulation, yalnızca son iki değer -> O(n) zaman, O(1) bellek
def climb_dp(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

DP çözme adımları

1. Durumu tanımla: dp[i] neyi ifade ediyor?
2. Geçiş formülünü yaz.
3. Taban durumlarını belirle.
4. Hesaplama sırasını seç (top-down veya bottom-up), sonra belleği optimize et.

Klasik DP problemleri: bozuk para üstü (coin change), en uzun ortak alt dizi (LCS), 0/1 knapsack, edit distance.