将SICP硬币找零Scheme代码转Python后不符合预期，问题出在哪？

问题背景 #

我正在阅读《计算机程序的构造和解释》（SICP）1.2.2节，其中给出了硬币找零问题的暴力实现Scheme代码：

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

LeetCode上的硬币找零问题要求为：输入coins = [1,2,5]、amount = 11，输出3，解释为11 = 5 + 5 + 1（即找零所需的最少硬币数量）。

我尝试将上述Scheme代码直译到Python，但未得到预期结果，疑惑为何两者逻辑看似相似却结果不同，我的Python实现代码如下：

def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0: return 1
        if amount < 0 or not coins: return 0

        # do not choose current coin
        return (self.coinChange(coins[1:], amount) + 
            self.coinChange(coins, amount - coins[0])) # choose current coin.

问题根源 #

核心目标完全不同 #

SICP中的count-change函数是计算凑成指定金额的硬币组合总数，比如对于金额11、硬币[1,2,5]，它会返回11（所有可能的组合数）；而LeetCode的问题是求凑成金额所需的最少硬币数量，目标从「计数」变成了「求最优解」，逻辑本质完全不一样。

递归逻辑与边界条件错误 #

你的Python代码直接照搬了SICP的累加逻辑，但LeetCode问题需要的是取最小值而非求和，具体错误点：

1. 边界条件错误：当amount == 0时，SICP返回1（代表找到一种有效组合），但LeetCode问题中此时应该返回0（不需要任何硬币）；当递归到amount < 0或无硬币可用时，SICP返回0（代表无效组合），但LeetCode问题中应该返回一个极大值（表示此路径不可行，不能参与最小值计算）。
2. 递归操作错误：SICP中用+累加两种选择的组合数，而LeetCode问题需要用min来选择「不用当前硬币」和「用当前硬币」两种路径中的最小硬币数。

修正后的Python实现示例 #

以下是符合LeetCode要求的递归实现（加入记忆化避免超时）：

from functools import lru_cache
from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @lru_cache(maxsize=None)
        def dp(n):
            if n == 0:
                return 0
            if n < 0:
                return float('inf')
            min_coins = float('inf')
            for coin in coins:
                sub_result = dp(n - coin)
                if sub_result != float('inf'):
                    min_coins = min(min_coins, sub_result + 1)
            return min_coins if min_coins != float('inf') else -1
        
        result = dp(amount)
        return result if result != float('inf') else -1

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