[数据结构与算法]322 零钱兑换

322 零钱兑换

递归版(超时)

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        int res =Integer.MAX_VALUE;
        for(int coin:coins){
            //子问题无解就跳过下面的步骤
            int subRes = coinChange(coins,amount-coin);
            if (subRes==-1){
                continue;
            }
            res = Math.min(res,subRes+1);
        }
        return res==Integer.MAX_VALUE?-1:res;
    }
}

动态规划

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0){
            return 0;
        }
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int coin:coins){
                if(i-coin<0 || dp[i-coin]==Integer.MAX_VALUE){
                    continue;
                }
                dp[i] = Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}

时间复杂度$O(amount?k)$，其中$k$是硬币数组的长度。
空间复杂度$O(k)$，需要开辟一个辅助数组。