C++ 中的硬币找零 2
c++server side programmingprogramming更新于 2024/9/1 18:20:00
假设我们有不同面额的硬币和总金额。我们必须编写一个模块来计算组成该金额的组合数。我们可以假设每种硬币的数量是无限的。因此，如果金额为 5 且硬币为 [1, 2, 5]，则有四种组合。 (1+1+1+1+1), (1+1+1+2), (1+2+2), (5)
为了解决这个问题，我们将遵循以下步骤 −
- 创建一个大小为 amount + 1 的数组 dp
- dp[0] := 1
- n := coins 数组的大小
- for i in range 0 to n – 1
- for j in range coins[i] to amount
- dp[j] := dp[j – coins[i]]
- for j in range coins[i] to amount
- return dp[amount]
示例(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
