221. Maximal Square.md

221. Maximal Square

Problem

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 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.

tag:

• dp

Solution

动态规划， 记dp[i][j]表示以i,j为右下角的正方形的最大正方形的边长，则状态转移方程：

dp[i][j] = min(dp[i-1][j-1]， dp[i-1][j], dp[i][j-1]);

java

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

go