動態(tài)規(guī)劃
- 思路：
- 假設(shè) dp[i] 為金額 i 使用零錢的組合數(shù)，其可以由其中的一種零錢 coin 和 i - coin 組合；
- ?遍歷零錢數(shù)組，對每一種零錢 coin 進(jìn)行如下操作：
- 從 coin 到 amount 金額進(jìn)行遍歷，dp[j] = dp[j] + dp[j - coin]
- 初始值，dp[0] = 1
-
上述做法不會重復(fù)計算不同的排列。因為外層循環(huán)是遍歷數(shù)組 coins 的值，內(nèi)層循環(huán)是遍歷不同的金額之和，在計算 dp[i] 的值時，可以確保金額之和等于 i 的硬幣面額的順序，由于順序確定，因此不會重復(fù)計算不同的排列。
class Solution {
public:
int change(int amount, vector<int>& coins) {
std::vector<int> dp(amount + 1);
dp[0] = 1;
for (int & coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
};?????——————————————————————文章來源：http://www.zghlxwxcb.cn/news/detail-820507.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-820507.html
到了這里，關(guān)于力扣518. 零錢兌換 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
