Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumknapsack-subset-dp

Coin Change II

Problem (yeniden ifade)

Verilen para birimleriyle amount’u oluşturan kombinasyon sayısı (sıra önemli değil).

Sezgi

Dış döngü paralar, iç miktar artan → permütasyon değil kombinasyon.

Yaklaşımlar

Sınırsız knapsack sayımı

Doğrulanmadı

Zaman O(amount · n)Alan O(amount)

Fikir. dp[0]=1; for coin: for a=coin..amount: dp[a]+=dp[a-coin].

Yürüyüş. amount=5, coins=[1,2,5] → 4.

Trade-off. Döngü sırasını değiştir → permütasyonlar (bu problem için yanlış).

Çözüm

export function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a]! += dp[a - c]!;
  }
  return dp[amount]!;
}

export function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a]! += dp[a - c]!;
  }
  return dp[amount]!;
}

Şablon bağlantısı

Sınırsız knapsack kombinasyonları.

Yansıma

Kombinasyon için dış döngü sikke, iç döngü amount. Tersi permütasyon sayar, 1+2 ile 2+1 iki kez girer.
dp[0] = 1. Amount 0 cevap 1. Sikke 0 yok.
Sırasız. Aynı sikke bir amount içinde birden fazla kez kullanılabilir.