C ++中的硬币更改2
假设我们有不同面额的硬币和总金额。我们必须编写一个模块来计算构成该数量的组合的数量。我们可以假设每种硬币有无限数量。因此，如果数量为5，硬币为[1、2、5]，则有四个组合。（1+1+1+1+1），（1+1+1+2），（1+2+2），(5)
为了解决这个问题，我们将遵循以下步骤-
创建一个大小为d+1的数组dp
dp[0]：=1
n：=硬币阵列的大小
对于i，范围为0至n–1
dp[j]：=dp[j–硬币[i]]
范围内的硬币j[i]等于
返回dp[金额]
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector <int> dp(amount + 1);
dp[0] = 1;
int n = coins.size();
for(int i = 0; i < n; i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
main(){
Solution ob;
vector<int> v = {1,2,5};
cout << (ob.change(5, v));
}输入值
5 [1,2,5]
输出结果
4