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

Mediumone-dimensional-dp

Coin Change

Problem (yeniden ifade)

Madeni para birimleri ve miktar verildiğinde, o miktarı oluşturan en az para sayısını döndür; imkânsızsa -1. Her birimden sınırsız kullanılabilir.

Sezgi

dp[x] = x yapmak için min para. dp[0]=0; her miktar için her parayı dene: dp[x] = min(dp[x], dp[x-coin]+1).

Yaklaşımlar

Aşağıdan yukarı DP

Tested only

Time O(amount · coins)Space O(amount)

Fikir. dp’yi ∞ ile başlat, dp[0]=0 hariç. Her para için geçişleri gevşet.

Adım adım. coins=[1,2,5], amount=11 → dp[11]=3 (5+5+1).

Trade-off’lar. Standart optimal. Para sayısına göre BFS de çalışır (para grafında en kısa yol).

Solution

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]! > amount ? -1 : dp[amount]!;
}

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]! > amount ? -1 : dp[amount]!;
}

Şablon bağlantısı

Klasik sınırsız knapsack / 1D DP.

Yansıma

Hangi kalıp bunu 90 saniyede ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozardı?