Maximal Rectangle

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

答案
类似Maximal Square，但是是错误的dp解法
因为你没法完全根据左边，上边，和左上角的三个cell的dp值来决定当前cell的dp值

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][][][] dp = new int[rows][cols][3][2];
        int max_area = 0;
        // base case dp[0][0]
        if(matrix[0][0] == '1') {
            for(int i = 0; i < 3; i++) {
                int w = 1, h = 1;
                dp[0][0][i][0] = w;
                dp[0][0][i][1] = h;
                max_area = Math.max(max_area, w * h);
            }
        }

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                // Skip base case
                if(i == 0 && j == 0) continue;
                // Skip '0' case
                if(matrix[i][j] == '0') continue;

                // Choice 0
                int w = 1;
                int h = 1 + ((i > 0) ? dp[i - 1][j][0][0] : 0);
                dp[i][j][0][1] = w;
                dp[i][j][0][0] = h;
                max_area = Math.max(max_area, w * h);

                // Choice 1
                w = 1 + ((j > 0) ? dp[i][j - 1][1][1] : 0);
                h = 1;
                dp[i][j][1][1] = w;
                dp[i][j][1][0] = h;
                max_area = Math.max(max_area, w * h);

                // Choice 2
                w = 1 + ((i > 0 && j > 0) ? Math.min(dp[i - 1][j - 1][2][1], dp[i][j - 1][1][1]) : 0);
                h = 1 + ((i > 0 && j > 0) ? Math.min(dp[i - 1][j - 1][2][0], dp[i - 1][j][0][0]) : 0);
                dp[i][j][2][1] = w;
                dp[i][j][2][0] = h;
                max_area = Math.max(max_area, w * h);
            }
        }

        return max_area;
    }
}

正确答案
从这个题学会了:
有时候dp题，你并不能直接找到recurrence用以直接计算答案
但是你可以找到相关的其他变量x来计算recurrence，然后再用x来计算你所需的答案

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length, max_area = 0;

        // dp[i][j] records how many consecutive 1's from left to grid[i][j]
        int[][] dp_horz = new int[rows][cols];
        for(int i = 0; i < rows; i++)
            if(matrix[i][0] == '1') dp_horz[i][0] = 1;

        for(int i = 0; i < rows; i++) {
            for(int j = 1; j < cols; j++) {
                if(matrix[i][j] == '0') continue;
                dp_horz[i][j] = dp_horz[i][j - 1] + 1;
            }
        }

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(matrix[i][j] == '0') continue;

                // How many consecutive 1's to the left of matrix[i][j]
                int left1s = dp_horz[i][j];

                // Iterate up
                int min_w = left1s;
                for(int k = i; k >= 0; k--) {
                    int h = i - k + 1;
                    int w = dp_horz[k][j];
                    if(w < min_w) min_w = w;
                    int area = h * min_w;
                    max_area = Math.max(max_area, area);
                }
            }
        }
        return max_area;
    }

}