[322][中等][动态规划][背包][DFS] 零钱兑换

题目描述

322. 零钱兑换

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

示例 1:

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

示例 2:

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

说明:

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

解题思路

动态规划

与[279][中等][动态规划][背包][BFS] 完全平方数很相似, 只是由于1可能不存在, 因最终可能没有答案. 按照每次考虑添加一个硬币, 从0逐渐推算到总金额. 考虑状态dp[i][v]表示使用前i种硬币, 构成总金额为v的最少硬币数量. 我们使用inf代表没有组合方案, 以方便比较最小值, 简化状态转移方程, 在最后输出答案的时候, 按题目要求转换成-1即可.

滚动数组优化空间复杂度的版本.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[-1] if dp[-1] != float('inf') else -1

或者这样考虑, 对于总金额v, 遍历所有硬币情况, 去掉这个硬币, 取其中的最小值. 当去掉某个硬币后总金额小于0, 说明方案不可行, 使用inf表示.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for coin in coins:
                dp[i] = min(dp[i], (dp[i - coin] if i - coin >= 0 else float('inf')) + 1)
        return dp[-1] if dp[-1] != float('inf') else -1

DFS

使用动态规划的思路, 其实是自下而上, 即从0逐渐推算到最后的总金额n. 我们也可以转化成自上而下的思路, 这就是DFS的思路. 再使用LRU缓存中间结果, 防止重复计算.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @lru_cache(None)
        def dfs(number):
            if number == 0:
                return 0
            if number < 0:
                return float('inf')

            min_count = float('inf')
            for coin in coins:
                min_count = min(min_count, dfs(number - coin) + 1)
            return min_count

        ans = dfs(amount)
        return ans if ans != float('inf') else -1