和完全背包问题类似
定义dp[i][j]为前i个硬币，能够组成价值为j时硬币数的最小值
if(coins[i]<=j)
dp[i+1][j] = min(dp[i][j],dp[i+1][j-coins[i]]+1)
else
dp[i+1][j]=dp[i][j]
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.
AC代码：
/*
和完全背包问题类似
定义dp[i][j]为前i个硬币，能够组成价值为j时硬币数的最小值
if(coins[i]<=j)
dp[i+1][j] = min(dp[i][j],dp[i+1][j-coins[i]]+1)
else
dp[i+1][j]=dp[i][j]
*/
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 1000000));
//初始化边界条件
for (int i = 0; i < coins.size(); i++)
{
if (coins[i] <= amount)
dp[0][coins[i]] = 1;
}
//初始化边界条件
for (int i = 0; i < dp.size(); i++)
{
dp[i][0] = 0;
}
//进行动态规划
for (int i = 0; i<coins.size(); i++)
{
for (int j = 0; j <= amount; j++)
{
if (coins[i] <= j)
dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - coins[i]] + 1);
else
dp[i + 1][j] = dp[i][j];
}
}
if (dp[coins.size()][amount] == 1000000) return -1;
else return dp[coins.size()][amount];
}
};