动态规划
- 思路:
- 假设 dp[i] 为金额 i 使用零钱的组合数,其可以由其中的一种零钱 coin 和 i - coin 组合;
- 遍历零钱数组,对每一种零钱 coin 进行如下操作:
- 从 coin 到 amount 金额进行遍历,dp[j] = dp[j] + dp[j - coin]
- 初始值,dp[0] = 1
-
上述做法不会重复计算不同的排列。因为外层循环是遍历数组 coins 的值,内层循环是遍历不同的金额之和,在计算 dp[i] 的值时,可以确保金额之和等于 i 的硬币面额的顺序,由于顺序确定,因此不会重复计算不同的排列。
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];
}
};
——————————————————————