DP Grid Basics¶
Table of Contents¶
- 64. Minimum Path Sum (Medium)
- 62. Unique Paths (Medium)
- 63. Unique Paths II (Medium)
- 120. Triangle (Medium)
- 3393. Count Paths With the Given XOR Value (Medium)
- 931. Minimum Falling Path Sum (Medium)
- 2684. Maximum Number of Moves in a Grid (Medium)
- 2304. Minimum Path Cost in a Grid (Medium)
- 1289. Minimum Falling Path Sum II (Hard)
- 3418. Maximum Amount of Money Robot Can Earn (Medium)
64. Minimum Path Sum¶
from functools import cache
from typing import List
# Iterative
def minPathSum(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# init
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = grid[i][0] + dp[i - 1][0]
for j in range(1, n):
dp[0][j] = grid[0][j] + dp[0][j - 1]
# update
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
# Recursive
def minPathSumDFS(grid: List[List[int]]) -> int:
INF = 10**18
@cache
def dfs(i, j):
if i < 0 or j < 0:
return INF
if i == 0 and j == 0:
return grid[i][j]
return min(dfs(i, j - 1), dfs(i - 1, j)) + grid[i][j]
return dfs(len(grid) - 1, len(grid[0]) - 1)
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print(minPathSum(grid)) # 7
print(minPathSumDFS(grid)) # 7
62. Unique Paths¶
"""
- Count the number of unique paths to reach the bottom-right corner of a `m x n` grid.
"""
# DP - 2D
def uniquePaths(m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
print(uniquePaths(m=3, n=7)) # 28
# [[1, 1, 1, 1, 1, 1, 1],
# [1, 2, 3, 4, 5, 6, 7],
# [1, 3, 6, 10, 15, 21, 28]]
#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
vector dp(m, vector<int>(n, 1));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
int main() {
int m = 3, n = 7;
cout << uniquePaths(m, n) << endl; // 28
return 0;
}
63. Unique Paths II¶
from functools import cache
from typing import List
class UniquePathsWithObstacles:
def memoization(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: DFS with Memoization
Time complexity: O(mn).
Space complexity: O(mn).
"""
@cache
def dfs(i: int, j: int) -> int:
if i < 0 or j < 0 or obstacleGrid[i][j]:
return 0
if i == 0 and j == 0:
return 1
return dfs(i - 1, j) + dfs(i, j - 1)
m, n = len(obstacleGrid), len(obstacleGrid[0])
return dfs(m - 1, n - 1)
def dp_2d(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: 2D Dynamic Programming
Time complexity: O(mn).
Space complexity: O(mn).
"""
# edge cases
if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# init dp
dp = [[0] * n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
# update dp
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
def dp_1d(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: 1D Dynamic Programming
Time complexity: O(mn).
Space complexity: O(n).
"""
n = len(obstacleGrid[0])
dp = [0] * (n + 1)
dp[1] = 1
for row in obstacleGrid:
for j, x in enumerate(row):
if x == 0:
dp[j + 1] += dp[j]
else:
dp[j + 1] = 0
return dp[n]
if __name__ == "__main__":
solution = UniquePathsWithObstacles()
obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
assert solution.dp_2d(obstacleGrid) == 2
assert solution.memoization(obstacleGrid) == 2
assert solution.dp_1d(obstacleGrid) == 2
120. Triangle¶
from functools import cache
from typing import List
class Solution:
# Recursive
def minimumTotalRecursive(self, triangle: List[List[int]]) -> int:
n = len(triangle)
@cache
def dfs(i, j):
if i == n - 1:
return triangle[i][j]
return min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]
return dfs(0, 0)
# Iterative
def minimumTotalIterative(self, triangle: List[List[int]]) -> int:
for i in range(len(triangle) - 2, -1, -1):
for j in range(i + 1):
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
return triangle[0][0]
if __name__ == "__main__":
solution = Solution()
triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
assert solution.minimumTotalRecursive(triangle) == 11
assert solution.minimumTotalIterative(triangle) == 11
3393. Count Paths With the Given XOR Value¶
931. Minimum Falling Path Sum¶
2684. Maximum Number of Moves in a Grid¶
from typing import List
# DFS
def maxMovesDFS(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
res = 0
def dfs(r, c):
nonlocal res
res = max(res, c)
if res == n - 1:
return
for k in r - 1, r, r + 1:
if 0 <= k < m and grid[k][c + 1] > grid[r][c]:
dfs(k, c + 1)
grid[r][c] = 0
for i in range(m):
dfs(i, 0)
return res
grid = [[2, 4, 3, 5], [5, 4, 9, 3], [3, 4, 2, 11], [10, 9, 13, 15]]
print(maxMovesDFS(grid)) # 3