Python实现动态规划bestSum函数结果与JS版本不一致问题排查

• 可变对象引用篡改：原JS代码中const combination = [...remainder_com, num]会创建全新数组，不会修改递归返回的原始结果。而你的Python代码直接对递归返回的partial调用append()，由于Python列表是可变引用类型，这个修改会直接改变memo中缓存的组合值，后续复用缓存时拿到的都是被篡改过的长数组，最终导致结果长度异常。
• 可变默认参数隐患：Python中函数的可变默认参数只会在函数定义时初始化一次，你写的memo:Dict[int, Any]={}会导致多次调用best_sum时复用同一个memo对象，产生跨调用的缓存串扰，属于隐藏bug。

1. 构造新组合时创建独立列表，不要修改递归返回的原始缓存值
2. 将memo默认值改为None，在函数内部初始化空字典，避免可变默认参数问题

from typing import Any, Dict, List, Optional


def best_sum(target: int, numbers: List[int], memo: Optional[Dict[int, Any]] = None) -> Optional[List[int]]:
    # 初始化memo，避免可变默认参数问题
    if memo is None:
        memo = {}
    if target in memo:
        return memo[target]

    if target == 0:
        return []

    if target < 0:
        return None

    shortest_combination: Optional[List] = None
    for num in numbers:
        partial = best_sum(target=target - num, numbers=numbers, memo=memo)
        if partial is not None:
            # 新建列表，不修改原partial的缓存值
            new_combination = partial + [num]
            if (shortest_combination is None) or (len(new_combination) < len(shortest_combination)):
                shortest_combination = new_combination

    memo[target] = shortest_combination
    return shortest_combination


if __name__ == "__main__":
    print(best_sum(target=100, numbers=[1, 2, 5, 25]))

测试best_sum(100, [1,2,5,25])会正确返回[25,25,25,25]，和JS版本结果一致。

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