# Rolling Array

## 2-D array, rolling in an array

1. The array has 2 states, cur and pre
2. If dp\[i] needs the updates from cur and pre, rolling from head; if dp\[i] needs the both updates from pre, rolling form tail

### 62 Unique Path

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).How many possible unique paths are there?

```java
// Tran: dp[i][j] = dp[i-1][j] + dp[i][j-1]
// Init: dp[i][0] = dp[0][j] = 0
// Ans: dp[m-1][n-1]
public int uniquePaths(int m, int n) {
    int[][] dp = new int[n][m];
    for(int i=0; i<n; i++) dp[i][0] = 1;
    for(int j=0; j<m; j++) dp[0][j] = 1;

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

* Improve 1: `dp[i][j]` only relates to `dp[i-1][j]`, `dp[i][j-1]`. We only needs to maintain 2 rows and switch the row every row iteration. Space O(2n)
* Improve 2: `dp[i][j]` can be update by just `dp[i-1][j]` and current `dp[i][j]`. Space O(n)

```java
public int uniquePaths(int m, int n) {
    int[] dp = new int[m];
    dp[0][0] = 1;

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

### 64 Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

1. Init first column and first column
2. f\[i]\[j] = min{f\[i-1]\[j], f\[i]\[j-1]} + A\[i]\[j]

```java
 public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] a = new int[m][n];
    a[0][0] = grid[0][0];

    // init row
    for (int i=1; i<m; i++){
        a[i][0] = a[i-1][0] + grid[i][0];
    }

    // init col
    for (int j=1; j<n; j++){
        a[0][j] = a[0][j-1] + grid[0][j];
    }

    for (int i=1; i<m; i++){
        for (int j=1; j<n; j++){
            a[i][j] = Math.min(a[i-1][j], a[i][j-1]) + grid[i][j];
        }
    }
    return a[m-1][n-1];
}
```

* Rolling array

```java
public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];

    for(int j=0; j<n; j++) dp[j] = j == 0 ? grid[0][j] : dp[j-1] + grid[0][j];

    for(int i=1; i<m; i++){
        for(int j=0; j<n; j++){
            if(j==0) dp[j] = grid[i][j] + dp[j];
            else dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);
        }
    }
    return dp[n-1];
}
```

### 72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

Insert a character Delete a character Replace a character

* State: f\[i]\[j]表示s1前i個字符經過幾次編輯可以變成s2前j個字符
* Func: f\[i]\[j] = f\[i-1]\[j-1], s1\[i-1]=s2\[j-1] 不用編輯

  f\[i]\[j] = 1+ min{f\[i-1]\[j-1],f\[i-1]\[j],f\[i]\[j-1]}

```python
def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
        
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                               # add          delete       replace
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                
    return dp[m][n]
```

* Rolling Array
* Use pre to record dp\[i-1]\[j-1]

```java
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int pre = 0;

    int[] dp = new int[n+1];

    for(int j=0; j<=n; j++){
        dp[j] = j;
    }

    for(int i=1; i<=m; i++){
        for(int j=0; j<=n; j++){
            int tmp = dp[j];
            if(j==0) dp[j] = i;
            else if(word1.charAt(i-1) == word2.charAt(j-1)) dp[j] = pre;
            else dp[j] = 1 + Math.min(pre, Math.min(dp[j], dp[j-1]));
            pre = tmp;
        }
    }

    return dp[n];
}
```

### 221. 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.

* State: dp\[i]\[j]是包含matrix\[i-1]\[j-1]的最小邊長&#x20;
* Func: if(matrix\[i-1]\[j-1]==1) dp\[i]\[j]=min(dp\[i-1]\[j],dp\[i]\[j-1],dp\[i-1]\[j-1])+1
* Ans: dp\[m+1]\[n+1]

![](https://2249014260-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LrHBOmnlXe2UPlScnAC%2F-LrHBQ9YsXQZtBYE5uIM%2F-LrHBS_QcPKbSNaVv9fu%2Fsquare.png?generation=1571189549925599\&alt=media)

1 Time O(m*n), Space O(m*n)

```java
public int maximalSquare(char[][] matrix) {
    if(matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int len = 0;

    int[][] dp = new int[m+1][n+1];

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; 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;
                len = Math.max(len, dp[i][j]);
            }
        }
    }
    return len*len;
}
```

2 Time O(m\*n), Space O(n)

* A value pre the record the dp\[i-1]\[j-1] value
* Update dp\[j] if not '1'

```java
public int maximalSquare(char[][] matrix) {
    if(matrix.length == 0 || matrix[0].length == 0) return 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int len = 0;
    int pre = 0;

    int[] dp = new int[n+1];

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            int tmp = dp[j];
            if(matrix[i-1][j-1] == '1'){
                dp[j] = Math.min(pre, Math.min(dp[j], dp[j-1]))+1;
                len = Math.max(len, dp[j]);
            }else{
                dp[j] = 0;
            }
            pre = tmp;
        }
    }
    return len*len;
}
```

\=> Compare [Maximal Rectangle](https://netjimmy.gitbook.io/code-interview-note/stack/increasing-stack)

## 304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

![](https://2249014260-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LrHBOmnlXe2UPlScnAC%2F-M45_mya0zIemSfBUnXd%2F-M46U27sYKq38D_0HyLD%2FRange_Sum_Query.png?alt=media\&token=e30a966c-7e27-438f-a768-be967ed5e131)

The above rectangle (with the red border) is defined by (row1, col1) = **(2, 1)** and (row2, col2) = **(4, 3)**, which contains sum = **8**

```python
class NumMatrix:
    """
    regionAB = regionOB - regionOA - regionOB + regionOA
    
    Pre-calculate region
    dp: i個row j個col組成的方形面積
    dp[i][j] = dp[i-1][j]+dp[i][j-1]+matrix[i][j]-dp[i-1][j-1]
    """
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]: return 
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                self.dp[i][j] = matrix[i-1][j-1] + self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 注意左上角的點是包含col and row的，左上角是dp[row][col]
        return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]
```