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