正方形子矩阵(medium)"/>
[dp]leetcode1277: 统计全为 1 的正方形子矩阵(medium)
题目:
1277. 统计全为 1 的正方形子矩阵
题解:
与221. 最大正方形一样的题,不过就是将计算最大边长改为计算最大边长的累加和。
代码如下:
class Solution {
public://与221.最大正方形思路是一样的,只不过将计算最大长度改成了计算最大长度的累加和int countSquares(vector<vector<int>>& matrix) {if(matrix.size()==0)return 0;int row=matrix.size(),col=matrix[0].size(),result=0;int dp[row+1][col+1];memset(dp,0,sizeof(dp));for(int i=1;i<=row;++i){for(int j=1;j<=col;++j){if(matrix[i-1][j-1]==1){dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;//正方形的边长result+=dp[i][j];//更新累加和}}}return result;}
};
更多推荐
[dp]leetcode1277: 统计全为 1 的正方形子矩阵(medium)
发布评论