使用 DP 的 python 中的子集总和

Question

我正在点击此链接为子集问题编写DP解决方案。

def subsetSum(input, target):
    row, col = len(input)+1, target+1
    db = [[False] * col] * row
    for i in range(row):
        db[i][0] = True
    for i in range(1, row):
        for j in range(1, col):
            db[i][j]=db[i-1][j]
            if db[i][j]==False and j>=input[i-1]:
                db[i][j] = db[i-1][j-input[i-1]]
    return db[i][j]
target = 5
input = [1,3,9,2]
subsetSum(input, target)

有趣的是，在每次迭代">j"之后，db[i-1](我们引用值的前一行(也在更新。我真的不知道这里发生了什么。请指教。

请找到此链接以获取打印的声明。

Answer 1

问题出在这一行 db = [[False] * col] * row .使用 * 运算符时，将创建引用原始列表的原始列表的副本。

请考虑以下示例：

l = [[1]*5]*3
print(l) # prints [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
l[0][0] = 0
print(l) # prints [[0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1]]

每个内部列表都引用同一对象。因此，当第一个列表的第一个元素发生更改时，所有列表似乎都会更改。

要解决此问题，您可以使用列表理解

：

l = [[1]*5 for _ in range(3)]
print(l) # prints [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
l[0][0] = 0
print(l) # prints [[0, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]

具体而言，您可以将分配给db的作业替换为以下内容：

db = [[False]*col for _ in range(row)] .