[数据结构与算法]动态规划 背包问题 322. Coin Change (Medium)

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Example 4:
Input: coins = [1], amount = 1
Output: 1
Example 5:
Input: coins = [1], amount = 2
Output: 2
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int m = coins.size();
        vector<vector<int>> dp(m+1, vector<int>(amount+1,amount+1));//最大值就是全用一元硬币的情况，也就是amount+1
        for(int i = 1; i <= m; i++){
            dp[i][0] = 0;
        }
        for(int i = 1; i <= m; i++){
            int weight = coins[i-1];
            for(int j = 1; j <= amount; j++){
                if(j >= weight){
                    dp[i][j] = min(dp[i-1][j], dp[i][j-weight] + 1);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }

            }
        }
        return dp[m][amount] == amount+1? -1 : dp[m][amount];
    }
};