OJ刷题---【算法课动态规划] 换硬币（C++完整代码）
·
题目：
给定面值分别为2，5，7的硬币，每种硬币有无限个，给定一个N，求组成N最少需要的硬币的数量，若无法组成则返回-1.
输入：
输入N (1<=N<=100)
输出：
输出需要的最少硬币个数。
完整代码（C++）：
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int coinchange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,amount+1);
dp[0] = 0;
for (int i = 1; i < dp.size(); i++)
for (int j = 0; j < coins.size(); j++)
{
if (i - coins[j] < 0) continue;
dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
};
int main()
{
Solution sol;
vector<int> s = { 2,5,7 };
int n;
cin >> n;
cout << sol.coinchange(s, n)<<endl;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)