Minimum Path Sum
Medium · 2-D Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
You are given an m x n grid of non-negative integers. Starting in the top-left cell and moving only right or down, you travel to the bottom-right cell.
The cost of a path is the sum of every cell it visits, including both corners. Return the smallest possible cost.
Examples
Input: grid = [[2,7,1],[3,1,4],[8,2,1]] Output: 9
The path 2 → 3 → 1 → 2 → 1 costs 9, the cheapest option.
Input: grid = [[5,0,0,9]] Output: 14
With a single row there is only one path.
Input: grid = [[1,9],[1,1]] Output: 3
Going down first avoids the 9.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
Approaches
- Baseline: relax every cell, one round per move — time O((m + n) · m · n), space O(m · n)
Follow-up
Now moves may go in all four directions (still non-negative costs). The cells no longer have a fixed order, so the table cannot be filled in one sweep; run Dijkstra from the top-left corner instead, in O(m · n · log(m · n)).
Related problems
Start free on Cariara · Coding problems · System design studio
