Snap: 322. Change of Change

力扣：322. 零钱兑换
题目：
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额.

计算并返回可以凑成总金额所需的 最少的硬币个数 .如果没有任何一种硬币组合能组成总金额,返回 -1 .
你可以认为每种硬币的数量是无限的.

dp【j】的含义:
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

递推公式：
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

初始化：
dp【0】为0的原因：amount是可以等于0的,At the same time, it is logically obviousdp【0】 = 0
因为dp[j]Choose the smaller of the two = min(dp[j], dp[j-coins[i]]+1);所以下标非0的元素都是应该是最大值.

遍历顺序：
This question is completely backpack type,So from childhood to adulthood 遍历,At the same time, the minimum number of coins required is not involved in the sequence,所以本题的两个forNesting of loops is not required,谁先谁后都行.

The reason for setting the judgment condition before the recursive function：
因为dp[j] = min(dp[j], dp[j-coins[i]]+1);If this operationdp[j - coins[i]] == INT_MAX那么dp[j-coins[i]]+1就越界了,So we need to set a judgment condition.

代码：

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 (dp[j - coins[i]] != INT_MAX) dp[j] = min(dp[j], dp[j-coins[i]]+1);
            }
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};