动态规划专题

leecode 221

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();if (n == 0) return 0; // 如果矩阵为空，则直接返回0  int m = matrix[0].size();vector<vector<int>> ans(n, vector<int>(m, 0)); // 初始化ans为n行m列的二维数组，并全部置为0  int maxSideLength = 0;// 初始化第一行和第一列  for (int i = 0; i < n; i++) {ans[i][0] = matrix[i][0] - '0'; // 假设矩阵中的字符是'1'或'0'，直接转换为整数  maxSideLength = max(maxSideLength, ans[i][0]);}for (int j = 0; j < m; j++) {ans[0][j] = matrix[0][j] - '0';maxSideLength = max(maxSideLength, ans[0][j]);}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (matrix[i][j] == '1') { // 使用'1'字符进行判断，而不是true  ans[i][j] = 1 + min(min(ans[i - 1][j - 1], ans[i][j - 1]), ans[i - 1][j]);maxSideLength = max(maxSideLength, ans[i][j]);}}}return maxSideLength * maxSideLength; // 因为返回的是最大正方形的面积，所以需要乘以边长本身  }
};

其实这个题目还可以使用二维前缀和来做

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;int a[101][101];
int b[101][101];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}// 计算前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];}}int len = 1;int ans = 0;while (len < min(n, m)) {for (int i = len; i <= n; i++) {for (int j = len; j <= m; j++) {if (b[i][j] - b[i - len][j] - b[i][j - len] + b[i - len][j - len] == len * len) {ans = max(ans, len);}}}len++;}cout << ans;return 0;
}