正方形(medium)"/>
[dp]leetcode221:最大正方形(medium)
题目:
题解:
- 动态规划
- 建立一个比原始矩阵维度多一的
dp[m+1][n+1]
数组,其中dp[i][j]
表示由“1”
构成的最大正方形的边长
- 状态转移方程:
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
- 可以看下图理解这个状态转移方程:
代码如下:
class Solution {
public://题解:动态规划,dp[i][j]表示由`1`构成的最大正方形的`边长`int maximalSquare(vector<vector<char>>& matrix) {if(matrix.size()==0)return 0;int row=matrix.size(),col=matrix[0].size(),maxLen=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;//取得正方形的边长maxLen=max(maxLen,dp[i][j]);//更新最大长度}}}return maxLen*maxLen;}
};
更多推荐
[dp]leetcode221:最大正方形(medium)
发布评论