322. Coin Change

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.

解题报告

这道题目的意思是从给出的数中找到若干个，使他们的和为一个定值。求所需的数的最小个数，如果不存在则输出-1。

这道题是典型的完全背包问题。

设想一下，对于值为x的数，如果amount-x可以被计算得到，那么也可以被计算得到。于是得到递推式：

dp[j] = min(dp[j], dp[j-coins[i]+1) //dp中存放的为计算得到j需要的最少的数字

初始条件

dp[0] = 0, dp[1..amount] = MAX;

代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        
        dp[0] = 0;
        for (int i=0;i<coins.size();i++){
            for (int j=coins[i];j<=amount;j++){
                dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
};