1. 題目

給你一個 m * n 的矩陣，矩陣中的元素不是 0 就是 1，請你統計并返回其中完全由 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 1504. 統計全 1 子矩形（記錄左側的連續1的個數）
LeetCode 5655. 重新排列后的最大子矩陣（前綴和+排序）

• dp[i][j] 表示 以(i,j)為右下角的最大正方形邊長
• 第一行、第一列肯定最大是1（矩陣值為1的話）
• 其他為 1 位置的最大邊長跟它相鄰的幾塊的關系：等于左上方向3個最短的邊長+1
• 正方形的個數等于最大的邊長
  

class Solution { public:int countSquares(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size(), i, j, count = 0;vector<vector<int>> dp(m,vector<int>(n,0));//dp[i][j] 表示 以i,j為右下角的最大正方形邊長for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(i==0 || j==0)dp[i][j] = matrix[i][j];//最多邊長1else if(matrix[i][j]==1)dp[i][j] = 1+min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]));count += dp[i][j];}}return count;} };

另評論區Gremist優化了內存，原地算法

class Solution { public:int countSquares(vector<vector<int>>& matrix) {int ans = 0;for (int i = 0; i < matrix.size(); i++) {for (int j = 0; j < matrix[0].size(); j++) {if (i && j && matrix[i][j]) {matrix[i][j] += min({matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]});}ans += matrix[i][j];}}return ans;} }; 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 1277. 统计全为 1 的正方形子矩阵（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。