二进制矩阵最大全1正方形面积求解DP代码运行原理解析咨询

这道题是典型的动态规划应用题，给定的JS代码通过动态规划的方式高效求解全1最大正方形的面积，具体逻辑如下：

核心定义 #

我们定义 dp[i][j] 表示：以矩阵第i行第j列的元素作为右下角时，能形成的全1正方形的最大边长。
状态转移的核心逻辑：如果当前位置matrix[i][j]是1，那么它能扩展出的最大正方形边长，由它上方、左侧、左上角三个位置的最小dp值决定——这三个位置分别对应了上方正方形的高度上限、左侧正方形的宽度上限、左上角正方形的对角线覆盖上限，最小的那个值决定了当前能扩展的最大边界，再加1就是当前位置的最大边长。

代码逐段解析 #

边界处理 #

if (!matrix.length || !matrix[0].length)
    return 0

处理空矩阵的特殊场景：如果矩阵行数为0，或者首行列数为0，直接返回面积0。

初始化DP数组与初始最大值 #

let dp = matrix.slice(), max = Math.max(...matrix[0])
for (let i = 0; i < matrix.length; i++) {
    max = Math.max(matrix[i][0], max)
}

• 这里直接浅拷贝输入矩阵作为DP数组，相当于原地修改输入矩阵存储DP值，不需要额外开辟O(mn)的辅助空间
• 初始最大值max先取第一行和第一列的最大值：因为第一行、第一列的元素没有足够的上方/左侧元素扩展，最多只能形成边长为1的正方形，所以先把边界的最大边长拿到。

核心状态转移遍历 #

for (let i = 1; i < matrix.length; i++) {
    for (let j = 1; j < matrix[0].length; j++) {
        if (matrix[i][j] == '0')
            continue
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        if (dp[i][j] > max)
            max = dp[i][j]
    }
}

从第二行第二列开始遍历所有非边界元素：

• 如果当前元素是'0'，不可能作为全1正方形的右下角，直接跳过
• 如果当前元素是'1'，按前面说的状态转移逻辑计算当前位置的最大边长
• 每次计算完当前dp值后，同步更新全局的最大边长max

结果返回 #

return max ** 2

题目要求返回正方形面积，直接对最大边长取平方即可。

内容的提问来源于stack exchange，提问作者Fraters TECHIE