Leetcode/各大家 -- 221. Maximal Square(DP)

221. Maximal Square(DP)
Medium
https://leetcode.com/problems/maximal-square/

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

 Apple Airbnb Facebook

思路： initialize dp[m+1][n+1], dp[i][j] indicating the max length of square at current position
           when a[i-1][j-1] = 1遇到1元素，dp[i][j]是左上，正上，左中的min +1

public class Solution {
    public int maximalSquare(char[][] a) {
      if(a == null || a.length == 0 || a[0].length == 0)return 0;
      int m = a.length, n = a[0].length;
      int[][] dp = new int[m+1][n+1];//is the max len of maximal square at current pos
      int max = 0;
      //dp: when a[i-1][j-1] = 1, dp[i][j] = 1 + Min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])
      for(int i = 1; i < m+1; i++){
          for(int j =1 ;j < n+1; j++){
              if(a[i-1][j-1] == '1'){
                  dp[i][j] = 1 + Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]));
                  max = Math.max(max,dp[i][j]);
              }
          }
      }
      return max*max;
    }
}