Mince na částku
O(n·amount)Pro dané hodnoty mincí a cílovou částku hledá coin change nejmenší počet mincí, které ji složí (každá hodnota je k dispozici bez omezení). Tabulka dp[i][a] drží nejlepší odpověď pro částku a s použitím prvních i hodnot. Každá buňka je lepší ze dvou možností: tuhle minci přeskočit (zkopírovat hodnotu z řádku nad) nebo použít ještě jednu (jedna plus buňka o `coin` sloupců vlevo ve stejném řádku, protože minci lze opakovat). Nedosažitelné částky zůstanou prázdné. Vyplnění tabulky je O(n·částka) a buňka vpravo dole je minimum. Je to učebnicový příklad optimální podstruktury s překrývajícími se podproblémy.
DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát
Jak to funguje
- Částka 0 vždy potřebuje 0 mincí — to je základní sloupec.
- Pro každou buňku nejprve zkopíruj odpověď, která tuhle minci přeskočí (řádek nad).
- Pokud se mince vejde, porovnej s 1 + buňka o hodnotu mince vlevo.
- Ponech menší; buňka vpravo dole je nejmenší počet mincí (prázdná = nemožné).
Pseudokód
1coinChange(coins, amount): # O(n·amount)2 dp[i][0] ← 0 # amount 0 needs 0 coins3 for each coin i, amount a in 1..amount:4 best ← dp[i-1][a] # skip this coin5 if a ≥ coin and dp[i][a-coin] reachable:6 best ← min(best, dp[i][a-coin] + 1) # reuse coin7 dp[i][a] ← best8 return dp[n][amount] # ∞ ⇒ impossible