// @Title: 零钱兑换 (Coin Change)
// @Author: qisiii
// @Date: 2024-10-31 23:53:41
// @Runtime: 28 ms
// @Memory: 44.2 MB
// @comment: 完全背包，但是初始化值和覆盖值要好好考虑
// @flag: GREEN
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[][] dp=new int[coins.length][amount+1];
        for(int[] d:dp){
            Arrays.fill(d,Integer.MAX_VALUE);
        }
        for(int j=0;j<=amount;j++){
            //刚好硬币可以凑够
            if(j%coins[0]==0){
                dp[0][j]=j/coins[0];
            }
        }
        for(int i=1;i<coins.length;i++){
            dp[i][0]=0;
        }
        for(int i=1;i<coins.length;i++){
            System.out.print("i="+i+" ");
            for(int j=1;j<=amount;j++){
                if(j>=coins[i]){
                    //只有凑得出的情况，才需要去修改
                    if(dp[i][j-coins[i]]!=Integer.MAX_VALUE){
                        dp[i][j]=Math.min(dp[i-1][j],1+dp[i][j-coins[i]]);
                    }else {
                        dp[i][j]=dp[i-1][j];
                    }
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[coins.length-1][amount]==Integer.MAX_VALUE?-1:dp[coins.length-1][amount];
    }
}