Minimum Path Sum

The key idea

The cheapest way to reach a cell is its own value plus the cheaper of the two cells you could have stepped from — the one above and the one to the left. So dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Fill the table in row-major order and the bottom-right cell holds the answer.

Problem

Given a m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Examples

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7

Input: grid = [[1,2,3],[4,5,6]] Output: 12

Complexity

Time: O(m * n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →