LeetCode 221 Maximal Square DP

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Solution

设 \(dp[i][j]\) 表示能到达位置 \((i,j)\) 的最大正方形边长。对于初始化，即 \(i=0 \text{ or } j=0\)，最大的边长就是该位置的数字；否则的话考虑转移：

\[dp[i][j] = 1+\min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) \]

即由周围的来进行限制，只能选最小的边长

点击查看代码

class Solution { private:     int dp[303][303];     int ans = 0; public:     int maximalSquare(vector<vector<char>>& matrix) {         if(matrix.empty())return 0;                  int n = matrix.size(), m = matrix[0].size();         for(int i=0;i<n;i++){             for(int j=0;j<m;j++){                 if((i==0)||(j==0)||(matrix[i][j]=='0')){                     dp[i][j] = matrix[i][j]-'0';                 }                 else{                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;                 }                 ans = max(ans, dp[i][j] * dp[i][j]);             }                      }         return ans;     }      };