Minimum Path Sum

Problem

You are given an m x n grid of non-negative integers. Starting at the top-left cell and moving only right or down, reach the bottom-right cell while collecting the smallest possible total of the cell values along the way (including both endpoints). Return that minimum total.

• Grid dimensions are small enough to fit comfortably in memory, typically well under a few hundred rows and columns.
• Cell values are non-negative and stay small enough that the running total never overflows an ordinary integer.

Examples

• grid = [[8,4,3],[5,4,9],[5,2,1]] → 19, via 8 → 4 → 4 → 2 → 1. A greedy solver that always steps to the smaller immediate neighbour would go right, right, down, down and walk straight through the 9, for a worse total of 25.
• grid = [[3,4,2],[1,5,7]] → 16, via 3 → 1 → 5 → 7 (down first, then right twice).
• grid = [[8]] → 8. A single cell is both start and finish.

Hints

1. Whatever the optimal route to the destination is, its final step comes from one of only two cells.
2. If you knew the cheapest way to reach every cell in the row above, could you compute the cheapest way to reach every cell in the current row?
3. 2D DP with dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), reducible to one row.