python回忆录

Question

我是动态编程方面的新手。这是一个python代码，用于通过回忆录找到与目标之和相加的数字的最短组合。

    global memo
    memo={}

    def bestSum(targetSum,arr):
        if targetSum in memo:
            
            return memo[targetSum]
    #Base conditions
            if targetSum==0:
                    return []
            if targetSum<0:
                    return None

            # Branching statments  
            shortestCombination=None
            for i in arr:
                    remainder_combination=bestSum(targetSum-i,arr)
                    if remainder_combination != None:
                            combination=remainder_combination
                            combination.append(i)
                            if shortestCombination ==None or len(shortestCombination)>len(combination):
                                    shortestCombination=combination
            
            memo[targetSum]=shortestCombination
            return shortestCombination



    print(bestSum(10,[1,4,5]))

但是输出是这样

4，1，4，1，5，1

而正确的输出是

5,5

如果我评论回忆录的陈述，输出将是正确的。这是没有回忆录的python代码.

    # global memo
    # memo={}

    def bestSum(targetSum,arr):
    #     if targetSum in memo:
            
    #         return memo[targetSum]
    #Base conditions
            if targetSum==0:
                    return []
            if targetSum<0:
                    return None

            # Branching statments  
            shortestCombination=None
            for i in arr:
                    remainder_combination=bestSum(targetSum-i,arr)
                    if remainder_combination != None:
                            combination=remainder_combination
                            combination.append(i)
                            if shortestCombination ==None or len(shortestCombination)>len(combination):
                                    shortestCombination=combination
            
            # memo[targetSum]=shortestCombination
            return shortestCombination



    print(bestSum(10,[1,4,5]))

上面的代码给了我正确的输出。

在java脚本中，也可以通过使用object获得相同问题的正确输出。

    const bestSum=(targetSum,numbers,memo={})=>{
    if(targetSum in memo) return memo[targetSum];
    if(targetSum===0) return  [];
    if(targetSum<0) return null;

    let shortestCombination =null;

    for (let num of numbers){
        reminderCombination=bestSum(targetSum-num,numbers,memo);
        if(reminderCombination !==null){
            const combination=[...reminderCombination,num]
            if(shortestCombination===null || combination.length< shortestCombination.length){
                shortestCombination=combination
            }
        }
    }

    memo[targetSum]=shortestCombination
    return shortestCombination
};

console.log(bestSum(10,[1,4,5]))

更多的例子很少

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

正确输出

7

10，10

3.

使用回忆录时输出错误

7

10，1，1，2，1，2，3，2，3，4，3，4，5，4，5，5，10

3，4，2，3，5，10，1，1，2，1，2，3，2，3，3，4，3，4，5，4，5，5

谢谢!

Answer 1

为了复制一个列表，我们必须使用copy()方法，而不使用它，我们是在引用列表而不是处理。

    memo={}
    def bestSum(targetSum,arr):
            if targetSum in memo:
                    return memo[targetSum]
            if targetSum==0:
                    return []
            if targetSum<0:
                    return None
            shortestCombination=None
            for i in arr:
                    remainder_combination=bestSum(targetSum-i,arr)
                    if remainder_combination != None:
                            combination = remainder_combination.copy()
                            combination.append(i)
                            if shortestCombination ==None or len(shortestCombination)>len(combination):
                                    shortestCombination=combination.copy()
            memo[targetSum]=shortestCombination
            return shortestCombination
    print(bestSum(10,[1,4,5]))