Python求解LeetCode221最大正方形时DP数组赋值异常问题求助

核心问题根源 #

你遇到的异常是Python列表浅拷贝导致的，问题出在dp数组的初始化代码：

dp=[[0]*rowleng]*colleng

• 第一步[0]*rowleng会生成一个独立的、包含rowleng个0的一维列表
• 第二步*colleng并没有生成colleng个独立的新列表，只是把第一步生成的列表的内存引用复制了colleng次，也就是说dp里所有的行都指向同一个列表对象
• 所以你修改dp[0][0]的时候，本质是修改了所有行共享的那个列表的第0位元素，最终表现出来就是所有行的第0位都变成了1

修复方案 #

把dp数组的初始化改成用列表推导式生成独立的二维数组，保证每一行都是互不影响的列表对象：

dp = [[0]*rowleng for _ in range(colleng)]

这种写法会为每一行生成新的独立列表，修改单一行的元素不会同步影响其他行。

修正后的完整代码 #

def maximalSquare(matrix):
    colleng = len(matrix)
    # 增加空矩阵边界判断，避免运行报错
    if colleng == 0:
        return 0
    rowleng = len(matrix[0])
    maxsqlst = []
    # 修正后的dp初始化
    dp = [[0]*rowleng for _ in range(colleng)]
    for i in range(colleng):
        for j in range(rowleng):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        maxsqlst.append(max(dp[i]))
    return max(maxsqlst)**2

修正后的代码可以正常通过你给出的测试用例，输出结果为4，符合预期。

内容的提问来源于stack exchange，提问作者RH W