动态规划
- 思路：
- 假设 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];
}
};——————————————————————
