322. 零钱兑换（Java）

1 题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 Java

将该问题看做动态规划问题，即将目标金额 amount 拆分成 0~amount 的 amount + 1 种不同金额的小问题

2.1 方法一（递归；正向暴力；超出时间限制）

先写状态方程

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 初始条件/特殊情况/出口函数
        if(amount == 0) return 0;

        int ans = Integer.MAX_VALUE;
        // 状态方程
        for(int coin: coins){
            if(coin > amount)   continue;   // 特殊情况
            int subProblem = coinChange(coins, amount - coin);
            if(subProblem == -1)    continue;   // 特殊情况

            ans = Math.min(ans, subProblem + 1);    // 核心方程
        }
        // 特殊情况
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

其实，上图中少一个状态：-1，当 Ci > n，且 i ∈ [1, k]（就是任意硬币面值 > 目标金额）
这样一来，代码就变成了：

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 特殊情况1
        if(amount == 0) return 0;
        // 特殊情况2
        Arrays.sort(coins);
        if(coins[0] > amount) return -1;

        int ans = Integer.MAX_VALUE;
        // 状态方程
        for(int coin: coins){
            int subProblem = coinChange(coins, amount - coin);
            if(subProblem == -1)	continue;	// *加上
            ans = Math.min(ans, subProblem + 1);    // 核心方程
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;	// *加
    }
}

还是觉得不太对，和斐波那契数列的那种递归有点不一样。
其实是因为特殊情况 2 返回 -1，导致比大小时（Math.min()）必须将 -1 的情况单另拿出来判断，将其改为返回MAX_VALUE就能归化到最基本的递归，结构十分清晰
见代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 特殊情况1
        if(amount == 0) return 0;
        // 特殊情况2
        Arrays.sort(coins);
        if(coins[0] > amount) return Integer.MAX_VALUE;

        int ans = Integer.MAX_VALUE;
        // 状态方程
        for(int coin: coins){
            ans = Math.min(ans, coinChange(coins, amount - coin));    // 核心方程
        }
        return ans + 1;
    }
}

递归（正向暴力）结构：
1特殊情况 / 初始条件 / 出口条件
2状态方程

2.2 方法二（自顶向下的动态规划）

对应2.1中第一个代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memory = new int[amount + 1];
        Arrays.fill(memory, -2);
        return coinChangeHelper(coins, amount, memory);
    }

    public int coinChangeHelper(int[] coins, int amount, int[] memory){
        // 查询备忘录
        if(memory[amount] != -2)    return memory[amount];

        // 初始条件/特殊情况/出口函数
        if(amount == 0) return 0;

        int ans = Integer.MAX_VALUE;
        // 状态方程
        for(int coin: coins){
            if(coin > amount)   continue;   // 特殊情况
            int subProblem = coinChangeHelper(coins, amount - coin, memory);
            if(subProblem == -1)    continue;   // 特殊情况

            ans = Math.min(ans, subProblem + 1);    // 核心方程
        }
        
        // 将每一步的结果都存储到备忘录中
        memory[amount] = (ans == Integer.MAX_VALUE ? -1 : ans);
        // 特殊情况-1
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

对应2.1中第二个代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memory = new int[amount + 1];
        Arrays.fill(memory, -2);
        return coinChangeHelper(coins, amount, memory);
    }

    public int coinChangeHelper(int[] coins, int amount, int[] memory){
        // 特殊情况1
        if(amount == 0) return 0;
        // 特殊情况2
        Arrays.sort(coins);
        if(coins[0] > amount) return -1;
        // 查询备忘录
        if(memory[amount] != -2)    return memory[amount];

        int ans = Integer.MAX_VALUE;
        // 状态方程
        for(int coin: coins){
            int subProblem = coinChangeHelper(coins, amount - coin, memory);
            if(subProblem == -1)	continue;	// *加上
            ans = Math.min(ans, subProblem + 1);    // 核心方程
        }
        
        // 将每一步的结果都存储到备忘录中
        memory[amount] = (ans == Integer.MAX_VALUE ? -1 : ans);
        return ans == Integer.MAX_VALUE ? -1 : ans;	// *加
    }
}

对应2.1第三段代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memory = new int[amount + 1];
        Arrays.fill(memory, -2);
        return coinChangeHelper(coins, amount, memory);
    }

    public int coinChangeHelper(int[] coins, int amount, int[]memory) {
        // 特殊情况1
        if(amount == 0) return 0;
        // 特殊情况2
        Arrays.sort(coins);
        if(coins[0] > amount) return Integer.MAX_VALUE;
        // 查询备忘录
        if(memory[amount] != -2)    return memory[amount];

        int ans = Integer.MAX_VALUE;
        // 状态方程
        for(int coin: coins){
            ans = Math.min(ans, coinChangeHelper(coins, amount - coin, memory));    // 核心方程
        }
        // 将每一步的结果都存储到备忘录中
        memory[amount] = ans + 1;

        return ans + 1;
    }
}

逆向暴力（递归）——> 自顶向下动态规划的步骤：
1、将递归方法存入字方法XXXXHelper，并加入备忘录memory
2、递归方法中查询备忘录，一般放在递归方法开头
3、递归方法末尾将结果存入备忘录，一般在return前

2.3 方法三（迭代；自底向上动态规划）

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 = 1; i <= amount; i++){
            for (int coin : coins)
                if (coin <= i)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

自顶向下——>自底向上：
1 将递归转化为迭代（就是一个for循环）
2 其它的地方要看情况改变，变动比较大

自底向上结构：
1 初始条件
2 迭代（for循环）
3 迭代内部包含状态方程