【重点!!!】【完全背包】【DP】322.零钱兑换

题目
本题思路参考
参考视频：灵茶山艾府
问：关于完全背包，有两种写法，一种是外层循环枚举物品，内层循环枚举体积；另一种是外层循环枚举体积，内层循环枚举物品。如何评价这两种写法的优劣？

答：两种写法都可以，但更推荐前者。外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。

法1：动态规划

Python

# 写法1
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [inf]*(amount+1) # dp[i]表示凑到i需要的最小硬币数
        dp[0] = 0 # 凑到金额0, 需要硬币数为0
        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] = min(dp[i-coin] + 1, dp[i])
        
        return -1 if dp[amount] > amount else dp[amount]


# 写法2
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [inf] * (amount + 1) # dp[i]表示凑到i元用的最小数量
        dp[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i - coin] + 1, dp[i])
        
        return -1 if dp[amount] > amount else dp[amount]

Java

// 时间复杂度：O(kN)
class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i]表示从coins[0, i]范围内组合成i的最小硬币数量
        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 (i >= coin) {
                    // min{不取当前coin, 取当前coin}
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);         
                }
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}