LeetCode 322. 零钱兑换

1、题目

image.png

2、分析

这个就是动态规划的题目了。
解决这类问题，可以使用递归也就是dp()函数，自顶向下的解决问题。也就是从dp(n)——>dp(0)
或者使用for循环，使用dp[]数组，自下向上解决问题。也就是从dp[0]---->dp[n]

第一种方法，最重要的就是递归函数dp(para)的参数是啥。
第二种方法，最重要的就是dp[para]的下标取什么。

假如coins = [1，2，5] ，目标金额是11
那么最小的硬币数，有以下几种可能，就是：

• 一个1元硬币，加上（11 - 1）的金额最小需要的硬币数；
• 一个2元硬币，加上（11 - 2）的金额最小需要的硬币数；
• 一个5元硬币，加上（11 - 5）的金额最小需要的硬币数

因此para就是：目标金额 - 硬币的面额

image.png

3、代码

第一种，自顶向下

class Solution {
    int[] memo = new int[10000];
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        if(amount < 0) return -1;
        //防止重叠子的问题
        if(memo[amount] != 0) return memo[amount];
        int res = Integer.MAX_VALUE;
        for(int coin : coins){
            //向下递归
            int sub = coinChange(coins, amount - coin);
            if(sub == -1) continue;
            res = Math.min(res, 1 + sub); //取子问题的结果 加一枚硬币
        }
        if(res == Integer.MAX_VALUE){
            memo[amount] = -1;
            return -1;
        }else{
            memo[amount] = res;
            return res;
        }
    }
}

第二种，自下向上

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