# 6/24, 滚动数组

潜水归来。刷起吧。

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

## [Unique Paths II](https://leetcode.com/problems/unique-paths-ii/)

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

```java
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](https://leetcode.com/problems/minimum-path-sum/)

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

```java
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](https://leetcode.com/problems/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

```java
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 也可以用滚动数组优化，不过貌似只能优化其中一个。

```java
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](https://leetcode.com/problems/maximal-rectangle/)

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/dong_tai_gui_hua/624-_dong_tai_gui_hua.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.