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;
}