【必备算法】动态规划：LeetCode题（六）322. 零钱兑换，518. 零钱兑换 II

322. 零钱兑换²

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

示例 1:

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

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

解法：动态规划

• 思路：分解模型&&重复子问题（==>求分解出的每个金额最少需要多少硬币组合）
  • 状态数组：d[i][j]。 前 i 种硬币凑成金额 j 需要的最少硬币
  • 初始状态：
    • d[0][j]=Integer.MAX_VALUE。没有硬币那就组不出 j，但这里不能用-1因为如果取min，那么结果一定全是-1
    • d[i][0]=0。凑出金额0要0个硬币（由于数组默认初始值是0，所以不用再显式声明）
  • 状态方程：d[i] = min(d[i-1][j], d[i][j-c[i-1]] + 1)。构成金额j就两种方式
  • 最终状态：d[coins.len][amount]。len个硬币组成最终金额amout
• 复杂度：
  • Time：O(n * amount)
  • Space：O(n * amount)

public int coinChange(int[] coins, int amount) {
        // 状态数组
        int[][] d = new int[coins.length + 1][amount + 1];
        // 初始状态          
        for (int j = 0; j <= amount; j++) d[0][j] = Integer.MAX_VALUE;
        // 状态递推
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                int useCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : Integer.MAX_VALUE;
                if (useCurCoin != Integer.MAX_VALUE) useCurCoin += 1;
                d[i][j] = Math.min(d[i - 1][j], useCurCoin);
            }
        }
        // 最终状态：d[coins.len][amount]
        return d[coins.length][amount] == Integer.MAX_VALUE ? -1 : d[coins.length][amount];
    }

518. 零钱兑换 II²

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

注意:

你可以假设：

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

解法一：分治（超时）

• 思路：分解模型（==>求分解出的每个金额可以有多少种组合方案）。递推公式，f(n) += f(n-coins[i]) i∈[0, coins.length)。

class Solution {
    public int change(int amount, int[] coins) {
        return changeConis(amount, 0, coins);
    }
    
	// start是防止重复答案（1,2,2）与 （2,2,1）
    // 比如在同一层，1 -> 2 // 2 -> 1
    private int changeConis(int money, int start, int[] coins) {
        if (money == 0) return 1;
        if (money < 0) return 0;

        int res = 0;
        for (int i = start; i < coins.length; i++) 
            res += changeConis(money - coins[i], i, coins);

        return res;
    }
}

解法二：动态规划

• 思路：
  • 状态数组：d[i][j]。使用前 i 种面值的硬币（即c中0~i-1的元素），凑成金额 j 的组合数
  • 初始状态：
    • d[i][0]=1,。组成金额0只有一种方式
    • d[0][i]=0。没有硬币时组合方式为0（注：由于数组默认初始值是0，所以不用再显式声明）
  • 状态方程：d[i][j] = d[i - 1][j] + d[i][j - c[i-1]] (j - c[i-1] >= 0)。i 种面值的组合 = i-1的组合 + i 组成 j-c[i]，（例如，d[3][5] = d[2][5] + d[3][0]）
  • 最终状态：d[coins.len][amount]。
• 复杂度：
  • Time：O（n * amount)
  • Space：O（n * amount)

最优子结构 = 选择 || 淘汰。这里的逻辑树其实存在淘汰重复分支的思路，与爬楼梯问题一样

public int change(int amount, int[] coins) {
        // 1.状态方程
        int[][] d = new int[coins.length + 1][amount + 1];
        // 2.初始状态
        for(int i = 0; i <= coins.length; i++) d[i][0] = 1;
        // 3.状态递推      
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                // 注：因为要保证j - coins[i-1] >= 0，所以先判断 d[i][j - c[i-1]]
                int userCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : 0;
                d[i][j] = d[i - 1][j] + userCurCoin;
            }
        }
        // 4.最终状态：d[coins.len][amount]
        return d[coins.length][amount];
    }