Leetcode最小硬币找零DP算法差异及性能优化疑问

两种实现代码 #

方法1：子集搜索+记忆化DFS #

def coinChange(self, coins: List[int], amount: int) -> int:
    def dfs(i, total, memo):
        key = (i, total)
        if key in memo:
            return memo[key]
        if total == 0:
            return 0
        if len(coins) == 0 or i >= len(coins):
            return inf
        count = inf
        if coins[i] <= total:
            res = dfs(i, total - coins[i], memo)
            if res != inf:
                count = res + 1
        memo[key] = min(count, dfs(i + 1, total, memo))
        return memo[key]
    return dfs(0, amount, {}) if dfs(0, amount, {}) != inf else -1

方法2：@lru_cache装饰的自顶向下DP #

def coinChange(self, coins: List[int], amount: int) -> int:
    @lru_cache(None)
    def dp(sum):
        if sum == 0: return 0
        if sum < 0: return float("inf")
        count = float('inf')
        for coin in coins:
            count = min(count, dp(sum - coin))
        return count + 1
    return dp(amount) if dp(amount) != float("inf") else -1

疑问解答 #

1. 第二种算法是否与子集测试逻辑一致？其for循环是否类似回溯法测试不同子集？ #

第二种算法的逻辑和子集测试不完全一致，但最终都覆盖了所有合法的硬币组合。它的for循环不是回溯式的子集枚举，而是从「凑出sum金额的最小硬币数」这个状态出发，枚举最后一步使用的硬币类型——也就是说，只要sum减去某枚硬币后的金额sum-coin能被凑出来，那sum的硬币数就是sum-coin的硬币数加1。这种思路是自顶向下的状态转移，和第一种「选/不选当前硬币」的子集枚举逻辑不同，但都能找到最优解。

2. 两种算法的核心差异是什么？ #

核心差异在于状态定义和枚举逻辑：

• 第一种算法的状态是(i, total)，表示考虑前i枚硬币时，凑出total金额的最小硬币数。枚举逻辑是「选当前硬币（可重复选，所以i不变）」或「不选当前硬币（i+1）」，本质是带重复选择的子集枚举+记忆化。
• 第二种算法的状态是sum，表示凑出sum金额的最小硬币数。枚举逻辑是「最后一步使用任意一枚硬币」，通过状态转移方程dp(sum) = min(dp(sum-coin) for coin in coins) + 1直接计算，状态维度更少（一维 vs 二维）。

3. 为何第二种算法速度更快？用字典给第二种算法实现记忆化效率骤降，给第一种加@lru_cache也无提升的原因？ #

• 第二种算法更快的核心原因：
  • 状态数量更少：第一种的状态数是O(n*amount)（n为硬币数量），第二种是O(amount)，状态数少了一个维度，整体计算量大幅减少。
  • lru_cache的底层优化：Python的@lru_cache是用C语言实现的哈希表，相比纯Python字典，它的访问、插入操作开销小很多，能显著降低递归的额外成本。
• 用字典给第二种算法做记忆化效率骤降：因为Python字典的所有操作（如键存在性检查、赋值）都是Python层面的逻辑，远不如C实现的lru_cache高效。
• 给第一种算法加@lru_cache无提升：即使加了缓存，第一种的状态数依然是O(n*amount)，远多于第二种的O(amount)，而且每次递归的分支判断逻辑更复杂，所以整体性能还是无法追上第二种算法。

内容的提问来源于stack exchange，提问作者cjames