close
The Coin Change Problem 題目看了一陣子才看懂，是指組成 n 元有多少硬幣元素(c)組合
這網站下的分類很詳細，原來換硬幣問題博大精深
https://smartkeyerror.com/Coin-Change
但我最後比較看懂的解法是
Youtube LeetCode 322. Coin Change and 518. Coin Change 2
大概就是說0元的時候0個硬幣也要算一種方法, dp[0]=1
dp[1],目標一元的時候，從元素湊有多少方法
dp[5],目標五元的時候，從元素湊有多少方法
假設元素1元，dp[5] 方法數是從dp[5-1]方法數累加出來的
元素如果大於n是湊不出來的所以可以略過
long[] dp = new long[(int)n + 1];
// 0 amount 0 coin also belong one way
dp[0] = 1;
// Go through all of the coins
for (int i = 0; i < c.size(); i++) {
int coin =Integer.parseInt(c.get(i)+"");
for (int j = coin; j <= n; j++) {
dp[j] += dp[(int)(j - c.get(i))];
}
}
return dp[(int)n];
文章標籤
全站熱搜
留言列表
美食 (2)
