数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中硬币找零 2
假设我们有不同面值的硬币和一笔总金额。我们必须编写一个模块来计算构成该金额的组合数。我们可以假设我们有每种硬币无限多枚。因此，如果金额为 5，硬币为 [1、2、5]，则有四种组合。(1+1+1+1+1)、(1+1+1+2)、(1+2+2)、(5)
为了解决这个问题，我们将遵循以下步骤 −
- 创建一个数组 dp，大小为金额 + 1
- dp[0] := 1
- n := 硬币数组的大小
- 对于范围从 0 到 n – 1 的 i
- 对于范围从硬币[i] 到金额的 j
- dp[j] := dp[j – 硬币[i]]
- 对于范围从硬币[i] 到金额的 j
- 返回 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
更新于:2020 年 4 月 29 日
420 次浏览
广告