leetcode 221. 最大正方形

爱被打了一巴掌 2023-06-08 06:43 20阅读 0赞

dp[i][j]表示以(i,j)为右下角的正方形最大的边长

转态转移方程:

  1. matrix[i][j]=='1':
  2. dp[i][j] = 1+min( dp[i-1][j-1], min( dp[i][j-1],dp[i-1][j] ));
  3. matrix[i][j]=='0':
  4. dp[i][j] = 0;

先初始化行和列

  1. class Solution {
  2. public:
  3. int maximalSquare(vector<vector<char>>& matrix) {
  4. int ret = 0;
  5. if( matrix.size()==0 ){
  6. return 0;
  7. }
  8. vector<vector<int> > dp(matrix.size(), vector<int>(matrix[0].size(),0));
  9. for(int i = 0;i < dp.size();i ++){
  10. if( matrix[i][0] == '1' ){
  11. dp[i][0] = 1;
  12. }else{
  13. dp[i][0] = 0;
  14. }
  15. ret = max(ret,dp[i][0]*dp[i][0]);
  16. }
  17. for(int i = 0;i < dp[0].size();i ++){
  18. if( matrix[0][i] == '1' ){
  19. dp[0][i] = 1;
  20. }else{
  21. dp[0][i] = 0;
  22. }
  23. ret = max(ret,dp[0][i]*dp[0][i]);
  24. }
  25. for(int i = 1;i < dp.size();i ++){
  26. for(int j = 1;j < dp[i].size();j ++){
  27. if(matrix[i][j]== '1'){
  28. dp[i][j] = 1;
  29. }else{
  30. dp[i][j] = 0;
  31. continue;
  32. }
  33. dp[i][j] += min( dp[i-1][j-1], min( dp[i][j-1],dp[i-1][j] ));
  34. ret = max(ret,dp[i][j]*dp[i][j]);
  35. }
  36. }
  37. return ret;
  38. }
  39. };

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,20人围观)

还没有评论,来说两句吧...

相关阅读

    相关 221. 正方形

    打卡!!!每日一题 今天继续给大家分享一道动态规划类型的题目,不过该题目的状态转移方程比较难以理解,我会详细的给大家分析一下 题目描述: > 在一个由 ‘0’ 和 ‘1’

    相关 Leetcode 221 正方形(DP)

    题目重述 在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。 示例 1: ![在这里插入图片描述][watermark