动态编程代码在 javascript 中有效，但在 python 中无效

Question

我正在从 freecodecamp 学习动态编程，讲师正在使用 JavaScript 并且我知道 python 所以我正在转换 python 中的逻辑。

长话短说，这个问题的 JavaScript 实现工作正常，但我的 python 实现给出了奇怪的输出。

我已经多次匹配语法和验证逻辑，我不能指出我哪里错了。任何帮助将不胜感激。

问题陈述：创建一个程序来查找总和等于 targetsum.

的最小整数子数组

JavaScript 实施：

const bestsum = (targetsum, numbers, memo={}) => {
    if (targetsum in memo) return memo[targetsum];
    if (targetsum === 0) return [];
    if (targetsum <0) return null;
    
    let shortestcomb = null;
    
    for (let num of numbers){
        const remainder = targetsum - num;
        const remaindercomb = bestsum(remainder, numbers, memo);
        if (remaindercomb !== null){
            const combination = [...remaindercomb, num];
            if (shortestcomb===null || combination.length < shortestcomb.length){
                shortestcomb = combination;
            }
        }
    }
    memo[targetsum] = shortestcomb;
    return shortestcomb;
}
console.log(bestsum(7, [2, 4, 3]));
console.log(bestsum(100, [1, 2, 5, 25]));

输出：

[ 3, 4 ]
[ 10, 10 ]

我的Python实现：

def bestsum(targetsum, arr, memo=None):
    if memo is None:
        memo={}
    if targetsum in memo: return memo[targetsum]
    if targetsum==0: return []
    elif targetsum < 0: return None
    shortest = None 
    for i in arr:
        remainder = targetsum-i
        seq = bestsum(remainder, arr, memo)
        if seq!=None:
            seq.append(i)
            if (shortest==None or len(seq)<len(shortest)):
                shortest = seq
    memo[targetsum] = shortest
    return shortest

print(bestsum(7, [2, 4, 3]))
print(bestsum(20, [5, 10]))

输出：

[4, 3]
[10, 5, 5, 10]

第二种情况的明显答案是 [10, 10] 因为元素数量最少总和为 20，同样对于第一种情况 JavaScript 输出是 [3, 4] 而python输出是[4, 3]，是不是很奇怪？

编辑：有人将此问题标记为重复，我遵循该指南并使用占位符代替可变默认参数，但输出仍然相同，现在出了什么问题？

Answer 1

虽然交互式调试器是检查 bug 的最通用（通常也是最强大）的方法，但这里的一些简单的脚手架可以揭示很多东西。通过在 bestsum 结束之前添加一条 print(f"target = {targetsum}; memo = {memo}") 语句，我们得到：

target = 5; memo = {5: [5]}
target = 10; memo = {5: [5, 5], 10: [10]}
target = 15; memo = {5: [5, 5, 10], 10: [10, 5], 15: [10, 5]}
target = 20; memo = {5: [5, 5, 10], 10: [10, 5, 5, 10], 15: [10, 5, 5, 10], 20: [10, 5, 5, 10]}

请注意每个目标总和的条目如何不断变化。根据算法，这不应该发生。查看bestsum，memo的条目来自seq。寻找改变 seq 的行，我们找到 seq.append(i)。这会改变列表，这就是 memo 的条目不断变化的原因，也是最终结果不正确的原因。 bestsum 的 JavaScript 版本为循环体的每次迭代创建一个新列表，这就是为什么它不会遭受此错误的原因。

请注意，您可以直接翻译 JavaScript 并使用扩展运算符，或者您可以列出连接：seq = seq + [i].

一种可以防止出现此错误的方法是使用不可变类型而不是列表。在 Python 中，那将是 tuple。一个问题是如果使用元组连接，single-element 元组必须有一个逗号尾随元素：seq = seq + (i,).

Answer 2

扩展@outis 的回答，memo 的条目随着每次迭代而变化，这不应该发生。发生这种情况是因为当您将列表分配给新变量时，python 将旧列表的地址引用到新变量，而不是创建新列表。

这会在列表更改时产生问题，因为更改开始显示在其所有副本中。

这里seq是主列表

shortest 复制自 seq

memo[targetsum] 复制自 shortest

理想情况下，在遍历递归树节点的所有子节点后，我们 select 将最短路径分配给 memo[targetsum] 但是 memo[target] 中的值随着 memo[target] 的变化而变化=14=] 在 memo.

中引入了意外的值

可以按照@outis 的建议使用不可变数据类型来修复它。但我们可以更进一步，只需对这段代码本身做一点小改动。

import copy
def bestsum(targetsum, arr, memo=None):
    if memo is None:
        memo = {}
    if targetsum in memo: return copy.deepcopy(memo[targetsum])
    if targetsum==0: return []
    elif targetsum < 0: return None
    shortest = None 
    for i in arr:
        remainder = targetsum-i
        seq = bestsum(remainder, arr, memo)
        if seq!=None:
            seq.append(i)
            if (shortest==None or len(seq)<len(shortest)):
                shortest = seq
    memo[targetsum] = copy.deepcopy(shortest)
    return shortest

print(bestsum(7, [2, 4, 3]))
print(bestsum(20, [5, 10]))

输出：

[3, 4]
[10, 10]

这里我们使用 python 中 copy 模块的 deepcopy。 deepcopy 本质上是创建一个新列表并用原始列表的元素递归填充它，因此新列表彼此完全不同。阅读更多相关信息 here

PS- deepcopy 在这里可能有点矫枉过正，因为它通常用于嵌套列表，使用 shallowcopy 在这里也可以正常工作。

浅拷贝语法-

newlist = oldlist.copy()

动态编程代码在 javascript 中有效，但在 python 中无效

Dynamic programming code works in javascript but not in python

javascript

python

dynamic-programming