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

た入场券 2022-12-20 01:52 155阅读 0赞

## [322. 零钱兑换²][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²][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];
        }

[322.]: https://leetcode-cn.com/problems/coin-change/
[518. _ II]: https://leetcode-cn.com/problems/coin-change-2/