322. 零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

示例 2：

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

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

解答

思路：完全背包介绍

完全背包 问题：有 $n$ 种物品，第 $i$ 种物品的体积为 $w[i]$，价值为 $v[i]$，每种物品可以 无限次重复选，求体积和不超过 $\text{capacity}$ 时的最大价值和。

回溯三问：

• 当前操作：枚举第 $i$ 件物品 选一个或者不选
• 当前问题：在剩余容量为 $c$ 时，从前 $i$ 种物品中得到的最大价值和
• 它的子问题：
  • 不选：在剩余容量为 $c$ 时，从前 $i-1$ 种物品中得到的最大价值和
  • 选：在剩余容量为 $c-v[i]$ 时，从 前 $i$ 种物品 中得到的最大价值和

递归方程：

$$\text{dfs}(i,c)=max(\text{dfs}(i-1,c),\text{dfs}(i,c-w[i])+v[i])$$

代码：完全背包回溯

def unbounded_knapsack(capacity: int, v: List[int], w: List[int]) -> int:
    n = len(v)

    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        
        if c < v[i]:
            return dfs(i - 1, c)
        
        return max(dfs(i - 1, c), dfs(i, c - v[i]) + w[i])
    
    return dfs(n - 1, capacity)

思路：记忆化搜索

这其实是完全背包的一种变形：每个硬币可以无限选，将硬币的个数看作硬币的价值，都是 1。那就是 恰好装 capacity 时，求最小的价值和（之前 494 求的是方案数，二者在边界返回值上有所不同）。

状态转移方程：

$$\text{dfs}(i,c)=min(\text{dfs}(i-1,c),\text{dfs}(i,c-w[i])+v[i])$$

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)

        @cache
        def dfs(i, c):
            if i < 0:
                return 0 if c == 0 else inf
            
            if c < coins[i]:
                return dfs(i - 1, c)
            
            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)
        
        ans = dfs(n - 1, amount)
        return ans if ans < inf else -1

思路：递推

改成递推方程：

$$f[i+1][c]=min(f[i][c],f[i+1][c-v[i]]+w[i])$$

注意起始条件。

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)

        f = [[inf] * (amount + 1) for _ in range(n + 1)]
        f[0][0] = 0 # 等价于 f[-1][0]

        for i, x in enumerate(coins):
            for c in range(amount + 1):
                if c < x:
                    f[i + 1][c] = f[i][c]
                else:
                    f[i + 1][c] = min(f[i][c], f[i + 1][c - x] + 1)
        
        ans = f[n][amount]
        return ans if ans < inf else -1

思路：空间优化

由于 f[i+1][c] 需要由 f[i][c] 也就是正上方，和 f[i+1][c-x] 也就是正左方的数转移过来，因此一维优化时，正好需要从左往右遍历。

这样做的空间复杂度为 $O(\text{amount})$。

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)

        f = [inf] * (amount + 1)
        f[0] = 0

        for x in coins:
            for c in range(x, amount + 1):
                f[c] = min(f[c], f[c - x] + 1)
        
        return f[amount] if f[amount] < inf else -1