程序填空题：找零钱问题的动态规划求解

已知不同面值的钞票，求如何用最少数量的钞票组成某个金额，求可以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额，则返回-1

例如：

钞票面值：[1,2,5]; 金额：11=5+5+1；需要3张。

钞票面值：[2]；金额：3；无法组成，返回-1。

钞票面值：[1,2,5,7,10]；金额：14=7+7，需要2张。

c++
#include<vector>
#include<iostream>
#include<stdlib.h>
using namespace std;

class Solution
{

public:
Solution(){}
~Solution(){}
int coinsChange(std::vector<int>& coins, int amount)
{
std::vector<int> dp;
for (int i = 0; i <=amount; i++)
{
dp.push_back(-1);
}
dp[0] = @@[0](3);
for (int i = 1; i <=amount; i++)
{
for (int j = 0; j <@@[ coins.size()](3); j++)
{
if (i-coins[j]>=0&&dp[i-coins[j]]!=-1)
//i-coins[j]>=0的等号不可忽略，等号存在时相当于在初始化coins向量的dp值为1
{
if (dp[i]==-1||dp[i]>dp[i-coins[j]]+1)
dp[i] = @@[dp[i - coins[j]] + 1](3);
}
}
}
return dp[amount];
}
};

int main()
{
Solution solve;
std::vector<int> coins;
coins.push_back(1);
coins.push_back(2);
coins.push_back(5);
coins.push_back(7);
coins.push_back(10);
cout << solve.coinsChange(coins, 14);
return 0;
}






答案：
第1空：0

第2空： coins.size()

第3空：dp[i - coins[j]] + 1