力扣221. 最大正方形
2023-12-16 08:34:09
动态规划
- 思路:
- 假设 dp[i][j] 是第 i 行,第 j 列为右底点最大正方形边长;
- 则对应的状态转移方程
- s[i][j] = '0', dp[i][j] = 0
- s[i][j] = '1' 时,
- 如果是第1行或者第一列,dp[i][j] = 1;
- 其余情况下,dp[i][j] 等于其为右底点边长为2的周围正方形格子最大正方形数中最小值 + 1;
- 使用 maxSide 记录最大边长;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return 0;
}
int maxSide = 0;
int row = matrix.size();
int column = matrix[0].size();
std::vector<std::vector<int>> dp(row, std::vector<int>(column));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < column; ++j) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = std::min(std::min(dp[i - 1][j], dp[i][j - 1]) , dp[i - 1][j - 1]) + 1;
}
maxSide = std::max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
};
文章来源:https://blog.csdn.net/N_BenBird/article/details/135027016
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!