LeetCode 322: 零钱兑换递归解法返回错误结果求原因分析

我尝试用朴素递归解决LeetCode 322零钱兑换问题（后续计划基于此实现记忆化或动态规划表格法）。问题要求：给定不同面额的硬币数组coins和总金额amount，返回组成该金额所需最少硬币数，无法组成则返回-1，每种硬币可无限使用。

错误的递归实现 #

def coinChange(self, coins: List[int], amount: int) -> int:
        if amount < 0:
            return -1
        min_choices = float('inf')
        def coinChangeHelper(coins, amount):
            if amount < 0 or (amount > 0 and not coins):
                return -1
            elif amount == 0:
                return 0
            min_choices = float('inf')
            choice1 = 1 + coinChangeHelper(coins, amount - coins[0])
            if choice1 > 0:
                min_choices = min(min_choices, choice1)
            choice2 = 1 + coinChangeHelper(coins[1:], amount)
            if choice2 > 0:
                min_choices = min(min_choices, choice2)
            return min_choices
        return coinChangeHelper(coins, amount)

当输入coins=[1,2,5]、amount=11时，这个解法返回5，而正确结果应为3（5+5+1）。

正确的递归实现 #

def coinChange(self, coins: List[int], amount: int) -> int:
        def coinChangeHelper(coins, amount):
            if amount < 0:
                return -1
            elif amount == 0:
                return 0
            min_choices = float('inf')
            for coin in coins:
                choices = 1 + coinChangeHelper(coins, amount - coin)
                if choices > 0:
                    min_choices = min(min_choices, choices)
            return min_choices
        result = coinChangeHelper(coins, amount)
        return -1 if result == float('inf') else result

正确解法每次递归调用时都允许选择所有硬币。

错误原因分析 #

我最初的思路来自伪代码min_coins = current cost + min(cost without using this coin, cost using this coin)，但实际实现完全偏离了这个逻辑，问题出在这几点：

• 错误的分支加1操作：choice2是「不使用第一个硬币」的分支，但我错误地给这个分支加了1。「不选当前硬币」的场景下，并没有选择任何硬币，不应该额外加1，正确的逻辑应该是直接递归coinChangeHelper(coins[1:], amount)，不需要加1。这会导致所有「不选第一个硬币」的路径都被多算一个硬币，最终统计的硬币数偏大。
• 分支语义偏差：伪代码想表达的是「对当前硬币，选或不选两种情况取最小值」，但我的实现中，choice2的逻辑变成了「强制选一个硬币，然后只用剩下的硬币凑金额」，完全违背了「不选当前硬币」的初衷。
• 无效分支的判断干扰：当coins[1:]为空且amount>0时，递归返回-1，此时choice2 = 1 + (-1) = 0，而我的判断条件是if choice2 >0才更新最小值，这会让这个无效分支被忽略，但核心错误还是分支的加1操作。

比如在计算amount=11、coins=[1,2,5]时，错误的加1操作导致大面额硬币的最优路径无法被正确统计，算法被迫走多次选小面额硬币的路径，最终得到错误的5枚硬币结果。

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