Medium Tabulation Dynamic Programming
In plain English: Find the cheapest path from the top-left to the bottom-right of a grid, moving only right or down.
Each cell's minimum cost is its own value plus the cheaper of the cell above or to the left — fill row by row in O(mn).
Prompt
Given an m x n grid of non-negative integers, find a path from top-left to bottom-right that minimizes the sum. You can only move right or down.
Try to write it from scratch before scrolling down.
Solution
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
for i in range(1, m):
dp[0] += grid[i][0]
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1]) # min of above, left
return dp[-1]
# Test: min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) == 7 (1->3->1->1->1)