Algorithm

Appearance

1277. 统计全为 1 的正方形子矩阵 ​

  • 题号：1277
  • 来源：LeetCode
  • 难度：中等
  • 标签：dp 矩阵
  • 语言：TypeScript
  • 解法：1 个
  • 作者：lmliheng
  • 最近更新：2026-09-27

TypeScript · O(m*n) 时间 · O(m*n) 空间 · 更新于 2026-09-27

dp[i][j] 为右下角最大正方形边长并累加计数

typescript
/**
 * @difficulty medium
 * @tags dp,矩阵
 * @time O(m*n)
 * @space O(m*n)
 * @note dp[i][j] 为右下角最大正方形边长并累加计数
 * @1277. 统计全为 1 的正方形子矩阵
 */

let matrix: number[][] = [[1, 0, 1], [1, 1, 0], [1, 1, 0]];
console.log(matrix);
let m: number = matrix.length;
let n: number = matrix[0].length;
let max: number = matrix[0][0];
let res: number = 0;
//dp[i][j]是以ij元素作为右下角元素的最大正方形边长
let dp: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0));
dp[0][0] = matrix[0][0];
res += dp[0][0];
for (let i = 1; i < m; i++) {
    dp[i][0] = matrix[i][0];
    res += dp[i][0];
}
for (let i = 1; i < n; i++) {
    dp[0][i] = matrix[0][i];
    res += dp[0][i];
}
for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; 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;
        res += dp[i][j];
    }
}
console.log(dp);
console.log(res);
export {};

源码：ts/leetcode/1277. 统计全为 1 的正方形子矩阵.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm