DSA problem
Minimum Path Sum
Given an m x n grid of non-negative integers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of the numbers along the path. You can only move either down or right at any step.
This problem is the additive cousin of "Unique Paths". Instead of counting paths we minimize their cost, but the underlying structure is identical: any optimal path arriving at cell (i, j) must come from either (i - 1, j) or (i, j - 1). So the recurrence is dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]), with the first row and first column filled by prefix sums (they have only one predecessor each).
A brute-force search would explore every monotone path, costing O(C(m + n - 2, m - 1)) operations — exponential in the grid dimensions. Memoization shrinks that to O(m * n) by caching the minimum cost from each cell to the destination. Bottom-up tabulation does the same work iteratively with a clean two-pass fill.
The optimal space-optimized version uses a single rolling row dp of length n. Initialize it with the prefix sums of the first grid row. For each subsequent row, set dp[0] += grid[i][0] (only one predecessor) and then for j >= 1 do dp[j] = grid[i][j] + min(dp[j], dp[j - 1]). The "old" dp[j] represents the cost from above; the "new" dp[j - 1] represents the cost from the left. This is O(m * n) time and O(n) space.
Examples
grid = [[1,3,1],[1,5,1],[4,2,1]]7grid = [[1,2,3],[4,5,6]]12grid = [[5]]5Constraints
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
- The robot may move only right or down at each step.
- The start is `(0, 0)` and the destination is `(m - 1, n - 1)`.
- All grid values are non-negative.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.