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.

DP

Time Complexity

O(n^n)

Space Complexity

O(n^n)

思路

size 1

size 2

1 1

size 3

1 1 1

1 1 1

1 1 1

dpi the largest all 1 square's size withi as the bottom right (including)/up left

base case

dp0 dp0 dpi

dp rule

dpi = min(dpi-1, dpi, dpi - 1 if matrixi == 1 else 0

keep one global_max

代码

public int maximalSquare(char[][] matrix) {    //corner case    if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;    int rows = matrix.length, cols = matrix[0].length;    int[][] dp = new int[rows][cols];    int max = 0;        for(int i = 0; i < rows; i++){        if(matrix[i][0] == '1') dp[i][0] = 1;        max = Math.max(dp[i][0], max);    }    for(int j = 1; j < cols; j++){        if(matrix[0][j] == '1') dp[0][j] = 1;        max = Math.max(dp[0][j], max);    }    for(int i = 1; i < rows; i++){        for(int j = 1; j < cols; j++){                if(matrix[i][j] == '1'){                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j- 1]), dp[i - 1][j - 1]) + 1;                    max = Math.max(dp[i][j], max);                }        }    }    return max*max;}