TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
- For top down, start at the end, and notice the following:
- The end result comes from [r - 1, c] or [r, c - 1]
- For bottom up, start at the beginning, and notice the following:
- All elements, except i j 0 are guaranteed to have an element at [r - 1, c] or [r, c - 1].
- Therefore, you don’t have to worry about the comparison being infinity when you are saving the minimum.
- And this is 2D DP, where you use the initial table and notice that:
- By going traditionally through each element in the each row, you are by definition doing Dynamic Programming (Coding).
- This is because:
- Each element relies on [r - 1, c] or [r, c - 1] to build upon, so you are filling those in in the order they should be filled in.
Complexity
Runtime
Space
if using 2D DP
Code
Bottom Up
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for r in range(m):
for c in range(n):
if r == c == 0:
continue
c1, c2 = inf, inf
if r > 0: # Up 1
c1 = grid[r - 1][c]
if c > 0: # left 1
c2 = grid[r][c - 1]
grid[r][c] += min(c1, c2)
return grid[-1][-1]Top Down
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@cache
def dfs(row, col):
if row == col == 0:
return grid[row][col]
sr1, sr2 = inf, inf
if col - 1 >= 0:
sr1 = dfs(row, col - 1)
if row - 1 >= 0:
sr2 = dfs(row - 1, col)
return grid[row][col] + min(sr1, sr2)
return dfs(m - 1, n - 1)Notes
Cards
START Basic Front: Minimum Path Sum Back: Sum up min of [r - 1, c] and [r, c - 1], keeping in mind that all elements except r c 0 are guaranteed to have one of these positions.
END