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?

// 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)

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]

 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

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]}

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]

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]的最小邊長

• 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]

1 Time O(mn), Space O(mn)

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'

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

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).

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

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]