力扣 1277「统计全为 1 的正方形子矩阵」:矩阵 DP 递推推导与原地复用解法实战解析(InterviewGuide 刷题笔记)

原创2026-10-12 11:37:311,381 阅读
文章标签:文档知识库教程

力扣 1277「统计全为 1 的正方形子矩阵」:矩阵 DP 递推推导与原地复用解法实战解析(InterviewGuide 刷题笔记)

本文基于 InterviewGuide 动态规划专栏中 1277 题的原创题解展开,完整保留原始解法代码,并补充递推关系的形式化推导、边界条件与剪枝逻辑、复杂度分析以及同仓库姊妹题的横向对比。读完本文,你将掌握一类「统计全 1 正方形 / 矩形子结构数量」的二维 DP 通用套路,并能直接套用到最大正方形、全 1 子矩形等高频面试题上。

一、题目概述

给你一个 m * n 的矩阵,矩阵中的元素不是 0 就是 1,请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

这里的子矩阵要求是正方形(边长可以取 1、2、3……),且内部元素全部为 1。边长不同的正方形都各自计入总数。

示例 1:

输入:matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出:15
解释:
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2:

输入:matrix =
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出:7
解释:
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示(数据范围):

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

数据规模决定了本题的目标算法:矩阵最大可达 300 x 300,全量枚举所有正方形子矩阵的朴素做法(枚举左上角 + 边长 + 逐一校验)复杂度高达 O(m * n * min(m,n)^2),在最坏情况下不可接受。因此本题的标准解法是二维动态规划(DP),将时间复杂度压缩到 O(m * n)。

二、核心思路:如何用 DP 表示「以某格为右下角的最大全 1 正方形」

1. 状态定义

令 dp[i][j] 表示以 matrix[i][j] 为右下角、边长为 dp[i][j] 的全 1 正方形的边长,也即:以 (i, j) 为右下角能形成的最大全 1 正方形的边长。

这个定义的关键洞察在于计数与边长的等价关系:

若以 (i, j) 为右下角的最大全 1 正方形边长为 k,那么以 (i, j) 为右下角的所有全 1 正方形一共有 k 个(边长分别为 1, 2, ..., k)。

例如示例 1 中右下角元素 matrix[2][3] = 1 最终计算得到的 dp[2][3] = 3,表示以它为右下角可以形成边长 1、2、3 共 3 个全 1 正方形,直接累加进答案即可。这样一来,统计问题就被转化成了求解每个格子的最大边长问题,最终答案就是所有 dp[i][j] 之和。

2. 递推公式推导

考虑一般位置 (i, j)(i > 0 且 j > 0),若 matrix[i][j] == 1,那么以它为右下角能形成的最大全 1 正方形,受制于它的三个邻居:

  • 左上角 (i-1, j-1):决定正方形的「斜向」延伸;
  • 正上方 (i-1, j):决定正方形的「纵向」延伸;
  • 正左方 (i, j-1):决定正方形的「横向」延伸。

三者中任意一个能支撑的全 1 正方形边长最短,就决定了当前位置的上限。因此转移方程:

dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1   (当 matrix[i][j] == 1 时)

该公式与经典题 221. 最大正方形 的转移方程完全一致,区别仅在于:221 题只求所有格子中 dp[i][j] 的最大值,而本题要求所有 dp[i][j] 的总和——这正是两道题之间「求最大 vs 求总数」的本质差异。

3. 边界条件与剪枝

  • 当 i == 0 || j == 0(第一行或第一列)时,(i, j) 作为右下角最多只能形成边长为 1 的正方形,即 dp[i][j] = matrix[i][j](0 或 1)。
  • 当 matrix[i][j] == 0 时,以它为右下角不可能形成任何全 1 正方形,dp[i][j] = 0。

在原文档的代码中,这两个边界情况通过一个 if (matrix[i][j] && i && j) 的条件判断一次性剪掉:只有「当前位置为 1」且「不在第一行、第一列」时才进入状态转移,其余情况 dp[i][j] 保持原值 matrix[i][j](恰好就是 0 或 1),同样可以参与累加。这种写法既节省了分支判断,也让边界逻辑统一到了累加语句里。

三、经典解法:DP + 剪枝(原地复用,C++)

原始题解采用原地 DP:直接在传入的 matrix 上改写,把计算得到的 dp[i][j] 覆盖写回 matrix[i][j],从而省去一整块 O(m * n) 的辅助 DP 数组,空间上只需 O(1) 额外开销。

执行用时:136 ms,在所有 C++ 提交中击败了 85.93% 的用户;内存消耗:18.8 MB,击败 50.00% 的用户(数据来自原文档提交记录)。

int countSquares(vector<vector<int>>& matrix) {

    int row = matrix.size();
    if (row == 0) return 0;
    int col = matrix[0].size();
    int res = 0;
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            if (matrix[i][j] && i && j) {//直接将
                // i=0,j=0,matrix[i][j] = 0这三种情况去除掉了
                matrix[i][j] += min({matrix[i-1][j-1],matrix[i][j - 1], matrix[i - 1][j]});
            }
            res += matrix[i][j];
        }
    }
    return res;
}

逐行解读

代码片段 作用
if (row == 0) return 0; 空矩阵兜底,避免访问 matrix[0] 越界
for (int i = 0; i < row; ++i) 外层循环 从上到下逐行处理,保证访问 matrix[i-1] 时上一行已被更新为 dp 值
for (int j = 0; j < col; ++j) 内层循环 从左到右逐列处理,保证访问 matrix[i][j-1] 时左侧已更新为 dp 值
if (matrix[i][j] && i && j) 三重剪枝:当前位置为 1(排除 0)、非第一行、非第一列,三者同时满足才进入转移
matrix[i][j] += min({...}) 等价于 dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1,因为当前位置本身为 1 所以 += 1
res += matrix[i][j]; 每个格子累加其 dp 值,即「以该格为右下角的全 1 正方形个数」

注意 std::min 使用了大括号初始化列表 min({a, b, c}),这是 C++11 引入的 std::min(initializer_list<T>) 重载,可以一次对三个值取最小,比嵌套 min(min(a,b), c) 更直观。

复杂度分析

  • 时间复杂度:O(m * n)——两层循环遍历矩阵中每个元素恰好一次,每个元素只做常数次比较与加法;
  • 空间复杂度:O(1) 额外空间——原地改写输入矩阵,没有申请任何辅助数组(不计算输入本身占用的空间)。

四、手动推演:用示例 1 验证递推正确性

对示例 1 的矩阵,按行优先顺序逐步演算(括号内为更新后的 dp 值):

初始:
[0, 1, 1, 1]
[1, 1, 1, 1]
[0, 1, 1, 1]

第一行 i=0:所有格子保持原值,累加 0+1+1+1 = 3
第二行 i=1:
  (1,0) 在首列,保持 1;累加 → 4
  (1,1) = 1 + min(0, 1, 1) = 1;累加 → 5
  (1,2) = 1 + min(1, 1, 1) = 2;累加 → 7
  (1,3) = 1 + min(1, 2, 1) = 2;累加 → 9
第三行 i=2:
  (2,0) 为 0,保持 0;累加 → 9
  (2,1) = 1 + min(1, 0, 1) = 1;累加 → 10
  (2,2) = 1 + min(1, 1, 2) = 2;累加 → 12
  (2,3) = 1 + min(2, 2, 2) = 3;累加 → 15

最终 res = 15,与题目给出的答案一致。其中 dp[2][3] = 3 恰好对应以右下角为基准的边长 3 的最大正方形,累加过程也自然统计了边长 1、2、3 的所有正方形。读者可自行用示例 2 做同样的手算验证(结果为 7),以加深对「累加 dp 值即等于统计个数」这一核心思想的理解。

五、仓库姊妹题串联:一题带三题

InterviewGuide 动态规划 Medium 题库中与本专题高度相关的题目还有以下三道,建议按顺序一起刷:

1. 221. 最大正方形——同源转移方程

同样定义 dp[i][j] 为以 (i, j) 为右下角的最大全 1 正方形边长,转移方程完全相同。区别在最终聚合:221 题维护 length = max(length, res[i][j]) 并返回 length * length(面积),而 1277 题把所有 dp[i][j] 求和。仓库中 221 题给出了一个显式开辟 vector<vector<int>> res(m, vector<int>(n, 0)) 辅助数组的版本,与 1277 的原地版本正好形成「开 DP 数组 vs 原地复用」两种写法的对照。

2. 5454. 统计全 1 子矩形——从「正方形」推广到「矩形」

这道题是 1277 的进化版:统计的不再是正方形,而是任意长宽的全 1 子矩形。它不能直接套用「min 三个邻居」的递推,因为矩形允许长宽不等。仓库题解给出的思路是:以每个 (i, j) 为左上角,向下向右扩展,用 col_max 记录当前行能延伸的最右列并逐行收缩(遇到 0 就更新右边界并 break),累加每次扩展得到的矩形个数。原文档称之为「竞赛题之一」,难度明显高于 1277,适合作为进阶练习。

3. 64. 最小路径和——二维 DP 边界处理范式

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 是另一类二维 DP 的代表,其「第一行 / 第一列单独初始化」的边界处理方式,与 1277 用 i && j 剪枝的思路互为印证。刷完这三题,你对二维网格类 DP 的「状态定义 → 转移方向 → 边界处理 → 原地复用」完整流程会形成体系化认知。

另外,动态规划专栏目录 中收录了 26 道 Medium 难度 DP 题(从最长回文子串到下降路径最小和),本文这道题位列其中;专栏的 LeetCode 使用指南 也说明了这套题目从 600 余道力扣题中精选 300+ 道、按 13 个标签分类整理的背景,适合校招、社招及转行求职者按标签逐类刷题。

六、面试要点与总结

  1. 「以右下角定义状态」是二维网格 DP 的黄金套路:当问题与「全 1 正方形/矩形子结构」相关时,优先考虑 dp[i][j] 表示以 (i, j) 为右下角(或左上角)的最优子结构,转移只依赖左、上、左上三个邻居,天然满足无后效性。
  2. 统计与极值的转换:dp[i][j] = k 意味着以该格为右下角存在边长 1..k 共 k 个全 1 正方形,所以「计数」可以通过对 dp 求和完成,这是本题与 221 题唯一的收尾差异。
  3. 原地复用的前提是遍历顺序正确:必须按「行递增、列递增」的顺序处理,保证用到的 dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j] 都已经被更新为 dp 值,才可以直接覆盖写回 matrix,从而把额外空间压到 O(1)。
  4. 一句话总结:本题以 min(左上, 上, 左) + 1 的递推式、O(m*n) 时间、O(1) 额外空间的原地 DP 完美解决,是面试中「矩阵 DP」类别的高频考点,务必能手写、能推导、能讲清正确性。
登录后查看全文
InterviewGuide