为何li[i].append(x)与li[i]=li[i]+[x]在组合总和DP中表现不同？

在实现LeetCode组合总和问题的动态规划解法时，出现了一个奇怪的现象：使用dp[i].append(x)会得到不符合预期的结果，而dp[i] = dp[i] + [x]却能正常运行，两者看似功能一致，实际表现完全不同。

问题代码复现 #

from copy import copy,deepcopy
from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[]]*(target+1)
        # storing the ways in which i th element can form 
        
        for i in range(1,target+1):
            for ele in candidates :
                if i - ele >=0 :
                    li = deepcopy(dp[i-ele])
                    if i == ele :
                        print(dp,'b',i,ele)
                        # dp[i].append([ele])  # 此写法结果异常
                        dp[i] = dp[i] + [[ele]] # 此写法结果正常
                        print(dp,'change')
                        continue 
                    else:
                        for listt in li :
                            print(i)
                            # dp[i].append(listt+[ele])  # 此写法结果异常
                            dp[i] = dp[i] + [listt+[ele]] # 此写法结果正常
        print(dp)
        return dp[-1]


candidates = [2,3,6,7]
target = 3
Solution().combinationSum(candidates,target)

核心原因解析 #

问题的根源出在dp数组的初始化方式，而非append和+操作本身：

• dp = [[]]*(target+1)这种写法，并没有创建target+1个独立的空列表，而是让dp中的每个元素都指向同一个空列表对象。也就是说，dp[0]、dp[1]、dp[2]...本质上是同一个列表的不同引用。
• 当使用dp[i].append(x)时，是直接在这个共享的列表上进行修改，所有dp的元素都会同步发生变化——因为它们指向的是同一个内存地址的列表，这就导致最终的dp数组完全混乱。
• 而dp[i] = dp[i] + [x]的操作，会先通过+生成一个新的列表（原列表内容加上新元素），然后将dp[i]的引用指向这个新列表。此时dp[i]就和原来共享的列表断开了关联，后续修改只会影响这个新列表，不会干扰其他dp元素，因此能得到正确结果。

正确的初始化方式 #

要避免这个问题，应该创建target+1个独立的空列表，改用列表推导式初始化：

dp = [[] for _ in range(target+1)]

使用这种方式初始化后，每个dp[i]都是独立的列表对象，此时再使用dp[i].append(x)就不会出现异常，结果完全符合预期。

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