Minimum Path Sum
Hard · rating 1800 · Dynamic Programming, Matrix
The first line contains r and c. The next r lines each have c non-negative integers. Starting at the top-left and moving only right or down, print the minimum possible sum of visited cells to reach the bottom-right.
Constraints: 1 ≤ r, c ≤ 500
Editorial
Approach
Each cell can only be reached from above or from the left, so the cheapest way to a cell is its own value plus the cheaper of those two predecessors. Fill the grid row by row and the bottom-right cell holds the answer.
Rolling array
Because a row only depends on the row above and the cell to the left, a single 1-D array of width c is enough.
dp = [inf] * c; dp[0] = 0
for i in range(r):
for j in range(c):
best = dp[j] if i else inf # from above
if j: best = min(best, dp[j-1]) # from left
if i == 0 and j == 0: best = 0
dp[j] = best + grid[i][j]
return dp[c-1]Complexity
Time: O(r·c). Space: O(c).
Related problems
- 0/1 Knapsack — Hard
- Coin Change (Count Ways) — Hard
- Edit Distance — Hard
- Minimum Subset Difference — Hard
- Word Break — Hard
- Coin Change — Hard