Python流量控制功能很奇怪

Question

我试图用DP解决背包问题。基本上，目标是查看我们是否可以将列表中的某些元素加起来最多占总和的一半。

def canPartition(nums):
"""
:type nums: List[int]
:rtype: bool
"""
run_sum = 0
for num in nums:
run_sum += num
if run_sum & 1 == 1:
return False
run_sum //= 2
n = len(nums)
dp = [[False] * (run_sum+1)] * (n+1)
for i in range(n+1):
dp[i][0] = True
for j in range(1, run_sum+1):
dp[0][j] = False
print("initial stage")
print(dp)
for i in range(1, 2):
for j in range(1, run_sum+1):
dp[i][j] = dp[i-1][j]
print("inner loop after operation 1:")
print(dp)
if j >= nums[i-1]:
print("inner loop after operation 2:")
print(i, j)
dp[i][j] |= dp[i-1][(j - nums[i-1])]
print(dp)
print(" ")
return dp[n][run_sum]
nums = [1, 2, 5]
canPartition(nums)

目标本身在这里并不那么重要。但是最后一个嵌套循环的流控制行为真的很奇怪。以下是打印结果。

initial stage
[[True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False]]
inner loop after operation 1:
[[True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False]]
inner loop after operation 2:
1 1
[[True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False]]
inner loop after operation 1:
[[True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False]]
inner loop after operation 2:
1 2
[[True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False]]
inner loop after operation 1:
[[True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False]]
inner loop after operation 2:
1 3
[[True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False]]
inner loop after operation 1:
[[True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False]]
inner loop after operation 2:
1 4
[[True, True, True, True, True], [True, True, True, True, True], [True, True, True, True, True], [True, True, True, True, True]]

您可以看到，即使整个嵌套循环的 i 值为 1，也不知何故，dp[i>1] 的值在循环中被修改了。甚至 j 从 1 到 4 也被修改了。就像循环中还有另一个"for i in range(("。有谁知道为什么会这样？我用python 3.6.1运行了代码

Answer 1

此行

dp = [[False] * (run_sum+1)] * (n+1)

创建对同一False列表的n + 1引用的列表。一个更简单的例子：

>>> x = [[False]]*3
>>> x
[[False], [False], [False]]
>>> x[0][0] = True
>>> x
[[True], [True], [True]]

你几乎从不想将*与列表一起使用;而是使用列表推导来获取独立的列表：

dp = [[False for _ in range(run_sum+1)] for _ in range(n+1)]

Answer 2

在这一行中

dp = [[False] * (run_sum+1)] * (n+1)

* (n+1)不会神奇地创建内部列表的副本。相反，它只是列出对同一列表的(n+1)引用。