322.零钱兑换

给你一个整数数组 coins,表示不同面额的硬币；以及一个整数 amount,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数.如果没有任何一种硬币组合能组成总金额,返回 -1.你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

1.一刷+动规

dp[i]=min dp[i-c_j]+1(j=0...n-1)，表示金额为i需要的最小硬币数量等于i减去已知币值需要最小金币数量加1。dp是从小往大进行遍历维护，比较恶心的地方在于dp[i]什么时候赋值为-1，仅当往下找的全部币值i-c_j不越下界时均使得dp[i-c_j]=-1时，则dp[i]赋值为-1。这里用一个初始化为一个极大值的标志位min来辅助判断，如果min没有被修改，则说明底层要么是i-coin越下界的要么是不能用硬币表示的。

如果写成递归的话要注意保存底层已经判断得出硬币数量的值，因为递归是从上层调用底层结果，反复搜索底层结果会超时。因此要开辟额外空间保存结果。

public int coinChange(int[] coins, int amount) {
    int[] dp=new int[amount+1];
    for(int i=1;i<dp.length;i++)
    {
        int min=Integer.MAX_VALUE;
        for(int coin:coins)
        {
            if(i-coin>=0&&dp[i-coin]!=-1)
                min=dp[i-coin]<min?dp[i-coin]:min;
        }
        if(min==Integer.MAX_VALUE) dp[i]=-1;
        else dp[i]=min+1;
    }
    return dp[amount];
}

2.二刷+背包

采用一维背包dp实现，表示金币和为 j 的最小组合数。统一初始化为Integer.MAX_VALUE，表示当前该金额数目还不能凑出来。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[]dp=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=0;i<coins.length;i++){
            for(int j=1;j<=amount;j++){
                if(j-coins[i]>=0&&dp[j-coins[i]]!=Integer.MAX_VALUE)dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==Integer.MAX_VALUE) return -1;
        return dp[amount];
    }
}