Tek Boyutlu DP

Nasıl düşünülür

dp[i]’yi sade dilde adlandır (i tutarı için min madeni para; i. ev üzerinden maks para). Daha önceki hücrelerle ifade et. Bağımlılıkları saygı gösteren sırada doldur. Yalnızca son birkaç hücre önemliyse alanı sıkıştır.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Doğrusal	dp[i] ← dp[i-1], dp[i-2]	Soygun, merdiven
Sınırsız knapsack-ish	Coin dış/iç döngü	Coin change
LIS tarzı	dp[i]=max j<i	O(n²) temel

Karmaşıklık temeli

Tipik O(n) veya O(n·W); alan O(n) veya yuvarlanmış O(1).

Şablondan probleme

1. dp[i] anlamı + temel durumlar yaz.
2. Geçişi yaz.
3. Döngü sınırlarını dikkat seç.
4. dp[hedef] (veya dp üzerinde max) döndür.

/** 1D DP template: Coin Change (fewest coins). dp[x] = min coins for amount x. */
export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x]!, dp[x - c]! + 1);
    }
  }
  return dp[amount]! >= INF ? -1 : dp[amount]!;
}

/** 1D DP template: Coin Change (fewest coins). dp[x] = min coins for amount x. */
export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x]!, dp[x - c]! + 1);
    }
  }
  return dp[amount]! >= INF ? -1 : dp[amount]!;
}