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.
Init first column and first column
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.
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]
