Leetcode 221 - Maximal Square（dp）

2019-11-10 18:31:38

字体：大中小

来源：转载

供稿：网友

题意

给定一个由01组成的矩形，要求找出矩形内由1组成的最大正方形面积。

思路

状态表示：d[i,j] $d[i, j]$ ，以位置为矩形右下角的最大正方形的边长。r[i,j] $r[i, j]$ ，第i行，到第j个位置的1的长度。c[i,j] $c[i, j]$ ，第j列，到第i个位置的1的长度。

转移方程：d[i,j]=min{d[i−1,j−1]+1,r[i,j],c[i,j]} $d[i, j] = min/{d[i - 1, j - 1] + 1, r[i, j], c[i, j]/}$

时间复杂度：O(n2) $O(n^2)$

代码

const int maxn = 505;class Solution {public: int d[maxn][maxn], r[maxn][maxn], c[maxn][maxn]; int maximalSquare(vector<vector<char>>& matrix) { int m = matrix.size(); if (m) { int n = matrix[0].size(), ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '1') { r[i][j] = (j ? r[i][j - 1] + 1 : 1); c[i][j] = (i ? c[i - 1][j] + 1 : 1); } else { r[i][j] = c[i][j] = 0; } d[i][j] = min(min(r[i][j], c[i][j]), i && j ? d[i - 1][j - 1] + 1 : 1); ans = max(ans, d[i][j]); } } return ans * ans; } return 0; }};

上一篇：离散事件模拟-银行管理

下一篇：如何在Windows Forms 应用程序中查看及打印Office文档