视频讲解：https://www.bilibili.com/video/BV14K411R7yv

https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html

1.本题要求找到组成对应对的金额的最小的组合数，或排序数，所以本题没有先遍历物品还是背包的说法，所以要使用一维滚动数组求结果，dp[j - coins[i]]这个就是不放这个物品的的组合数，该值加1即是加上该物品的组合数，本题和前面的几道题基本上是一样的思路，不同在于是取min值所以初始化要将除去背包容量为0的值初始化为INT_MAX。

CPP

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;

        for(int i = 0; i < coins.size(); i++){
            for(int j = coins[i]; j <= amount; j++){
                if(INT_MAX != dp[j - coins[i]]){
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == INT_MAX)return -1;
        return dp[amount];
    }
};