6/24, 滚动数组

潜水归来。刷起吧。

待刷类别: 记忆化搜索DP，博弈类DP，区间类DP，背包类DP，划分类DP

Unique Paths II

挺经典的 2D-array 上做 DP 问题。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) return 0;

        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) dp[j] = 0;
                else dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n];
    }
}

Minimum Path Sum

思路一样，都属于 2D-array 上的路径问题。考虑到没有负数，也不存在往回走的情况，因此这个问题的 optimal substructure 比较简单，只依赖于来路的两个位置。

public class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        for(int i = 1; i < cols; i++){
            grid[0][i] += grid[0][i - 1];
        }
        for(int i = 1; i < rows; i++){
            grid[i][0] += grid[i - 1][0];
        }

        for(int i = 1; i < rows; i ++){
            for(int j = 1; j < cols; j++){
                grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }

        return grid[rows - 1][cols - 1];
    }
}

Maximal Square

一年前不熟悉动态规划去硬想的时候，困扰了我有段时间的题。

首先不难判断出，这是一个在给定 2D-array 上直接做 DP 的问题，有天然的 overlap subproblems，因而重点在于 states 之间的关联和构造，寻找 optimal substructure.

正方形在 2D-array 上的定位相对简单，只需要有一个顶点，加上边长就可以，其中对于所有正方形，顶点位置固定。既然矩阵 DP 大多从左上向右下扫，用正方形右下角定位比较简便。

对于每一个位置 (i,j):

• 其边长向左扩展受限于 (i, j-1);

• 其边长向上扩展受限于 (i-1, j);

• 其边长向对角线扩展受限于(i-1, j-1);

因此，以(i,j) 为右下角的最大正方形边长，取决于以上三个点。Optimal substructure 确定。

剩下的优化就是滚动数组了，我们只需要保存前面一行以及当前行的左面，因此 int[2][cols].

循环初始化的细节要注意下，此外还要注意取mod的时候 % 是在最后，而不是 (i % 2) - 1

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int max = 0;

        int[][] dp = new int[2][cols];

        for(int i = 0; i < cols; i++){
            dp[0][i] = matrix[0][i] - '0';
            max = Math.max(dp[0][i], max);
        }

        for(int i = 1; i < rows; i++){
            dp[i % 2][0] = matrix[i][0] - '0';
            for(int j = 1; j < cols; j++){
                if(matrix[i][j] == '0'){
                    dp[i % 2][j] = 0;
                } else {
                    dp[i % 2][j] = Math.min(dp[i % 2][j - 1],
                                   Math.min(dp[(i - 1) % 2][j], 
                                            dp[(i - 1) % 2][j - 1])) + 1;
                }
                max = Math.max(dp[i % 2][j], max);
            }
        }

        return max * max;
    }
}

Maximal Square Follow Up

01矩阵里面寻找一个对角线为 1， 其他全为 0 的矩阵

这题 LintCode 上还没有，所以就自己开 IDE 写，自己测 test case 了。思路和上一题类似。

由于连续对角线构造的依然是正方形，我们可以以一样的状态定义和转移方程来定义 (i,j) = 以 (i, j) 为起点的最大 1 对角线正方形。

对于(i , j)，我们可以通过(i - 1, j - 1) 来判断在对角线方向可以延伸多长；然而同时也要保证在 (i, j) 左面的宽为1的矩形全部是 0，上面宽为1的矩形也全部是0，其长度至少要等于 (i - 1, j - 1) 上的对角线长度。如果条件都满足，则可以继续 extend.

因此从 optimal substructure 来讲，和 Maximal Square 非常相似，都是从【左】【上】【对角线】来寻找能 valid 延伸的最长距离，其中最短的那个作为当前位置的 bottleneck.

我们需要构造额外的两个 DP 矩阵，用于记录对于每个位置 (i, j) 能向上和向左延伸的最长连续 0 长度。 O(mn) 时间， O(mn) 空间。

leftLen 和 upLen 也可以用滚动数组优化，不过貌似只能优化其中一个。

public class Main {

    private static int maximalDiagnoal(int[][] matrix){
        if(matrix == null || matrix.length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] leftLen = new int[rows][cols];
        int[][] upLen = new int[rows][cols];

        int max = 0;

        for(int i = 0; i < cols; i++){
            if(matrix[0][i] == 0) upLen[0][i] = 1;
            max = Math.max(max, matrix[0][i]);
        }
        for(int i = 0; i < rows; i++){
            if(matrix[i][0] == 0) leftLen[i][0] = 1;
            max = Math.max(max, matrix[i][0]);
        }

        for(int i = 1; i < rows; i++){
            for(int j = 1; j < cols; j++){
                if(matrix[i][j] == 0){
                    leftLen[i][j] = leftLen[i][j-1] + 1;
                    upLen[i][j] = upLen[i-1][j] + 1;
                }
                max = Math.max(max, matrix[i][j]);
                // By default 0
            }
        }

        int[][] dp = new int[2][cols];

        for(int i = 0; i < cols; i++){
            dp[0][i] = matrix[0][i];
        }

        for(int i = 1; i < rows; i++){
            dp[i % 2][0] = matrix[i][0];
            for(int j = 1; j < cols; j++){
                if(matrix[i][j] == 1){
                    int diag = dp[(i-1) % 2][j-1];
                    int left = leftLen[i][j-1];
                    int up = upLen[i-1][j];

                    int min = Math.min(diag, Math.min(left, up));

                    dp[i % 2][j] = min + 1;
                    if(min + 1 > max){
                        max = min + 1;
                        System.out.println("Row : " + i + "  Col : " + j);
                        System.out.println("Current Max : " + (min + 1));
                    }
                }
            }
        }

        return max;
    }

    public static void main(String[] args){

        int[][] matrix1 =  {{0,1,1,0,0,1},
                            {1,0,0,1,0,1},
                            {0,1,1,0,0,1},
                            {1,1,0,1,0,1},
                            {1,0,0,0,1,0}};

        int[][] matrix2 =  {{1,0,0,0,0,1},
                            {0,1,0,0,0,1},
                            {0,0,1,0,0,1},
                            {0,0,0,1,0,1},
                            {0,0,0,0,1,0}};

        int[][] matrix3 =  {{1,0,0,0,0,1},
                            {0,1,0,0,0,1},
                            {0,0,1,0,0,1},
                            {0,0,0,1,0,1},
                            {0,0,1,0,1,0}};
        testRun(matrix1);
        testRun(matrix2);
        testRun(matrix3);

    }

    private static void testRun(int[][] matrix){
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("Max square with 1's only at diagnal : " + maximalDiagnoal(matrix));
    }
}

Maximal Rectangle

这题显然就比 Maximal Square 复杂了，因为只有一个边长无法确定矩形位置，更无法确定面积。因为多了一个变量，所以我们的 DP 要多加一个维度，dp[i][j][k] = 以(i, j) 为右下角，底边长度为 k 的最大矩形高度。时间复杂度为 O(n^3)

我不太建议也不太觉得面试会考这种三维的 DP... 这题其实更适合用 maximal histogram 的思路去做，等我之后再回来搞定这题。