leetcode221

小鱼儿 2021-12-19 04:11 317阅读 0赞 
  1. int maximalSquare(vector<vector<char>>& matrix) {
  2.         int height=matrix.size();
  3.         if(height==0)
  4.             return 0;
  5.         int width=matrix[0].size();
  6.         vector<vector<int>>  vec(height,vector<int>(width,0));
  7.         int result=0;
  8.         for(int i=0;i<height;i++)
  9.         {
  10.             for(int j=0;j<width;j++)
  11.             {
  12.                 if(matrix[i][j]=='1')
  13.                 {
  14.                     vec[i][j]=1;
  15.                     if(i>0&&j>0)
  16.                         vec[i][j]+=min(min(vec[i-1][j],vec[i][j-1]),vec[i-1][j-1]);
  17.                 }
  18.                 result=max(result,vec[i][j]);
  19.             }
  20.         }
  21.         return result*result;
  23.     }

本题是动态规划的题目，vec[i,j]记录的是以matrix[i,j]为右下角的所能构成的正方形区域的边长最大值。

递推公式，vec[i][j]+=min(min(vec[i-1][j],vec[i][j-1]),vec[i-1][j-1])，计算的是当前单元格的“左”、“上”、“左上”三个单元格的最小值，再+1。

转载于:https://www.cnblogs.com/asenyang/p/9787674.html

发表评论

表情：
评论列表 （有 0 条评论，317人围观）

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

相关阅读

    相关 Leetcode 221 最大正方形(DP)

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

    墨蓝墨蓝/ 0 赞/ 258 阅读