algorithm - 同一矩阵上的最大平方 dp

Question

https://leetcode.com/problems/maximal-square/description/中的问题Maximal Square很容易被DP 解决。但我没有创建一个新矩阵，而是在原始矩阵上进行了修改，但该方法在第 64 号测试用例中失败，请检查我的以下代码并帮助我找出缺失点。

def maximalSquare(self, matrix: List[List[str]]) -> int:

    for x in range(1,len(matrix)):
        for y in range(1,len(matrix[x])):
            if matrix[x][y] == '1':
                matrix[x][y] = str(int(min( matrix[x-1][y], matrix[x][y-1], matrix[x-1][y-1]))+1)

    return int(max([max(x) for x in matrix])) ** 2 if matrix else 0

标签： algorithmdynamic-programmingpython-3.7

Answer 1

我猜你没有处理极端情况。对我来说，这段代码运行良好，几乎没有什么变化。此外，这会运行得有点慢。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        m, n, res = len(matrix), len(matrix[0]), 0
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0) and (matrix[i][j] == '1'):
                    res = max(res, 1)
                elif int(matrix[i][j]) == 1:
                    matrix[i][j] = min(int(matrix[i-1][j]), int(matrix[i][j-1]), int(matrix[i-1][j-1])) + 1
                    res = max(res, matrix[i][j])
        return res ** 2

迭代第一行或第一列时，dp(i, j) 的公式会检查是否有超出范围的值。通过将整个 dp 向右和底部移动 1 并将 0 的填充添加到第一行和第一列，它使公式在不检查边界的情况下工作。