Problem 29.3 · DP on GridsMedium

Minimum Path Sum

What it teaches: Cheapest path with min instead of sum of counts.

Practise it on judges as “Minimum Path Sum”.

The problem

Moving only right or down, find a path from the top-left to the bottom-right that minimises the sum of the numbers on it.

Example 1

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

1 → 3 → 1 → 1 → 1.

Constraints

1 ≤ m, n ≤ 200
0 ≤ values ≤ 200

Pattern clues in the wording

→ Minimum cost path with right/down moves

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int minPathSum(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	grid = [[1,3,1],[1,5,1],[4,2,1]]	7
2	grid = [[1,2,3],[4,5,6]]	12

From slow to fast

Approaches

1. One-row DP · O(m × n)

One-row DP

Time O(m × n) Space O(n)

dp[c] holds the row above; update left to right with min(dp[c], dp[c − 1]).

Approach 1

import java.util.Arrays;

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int[] row : grid)
            for (int c = 0; c < n; c++)
                dp[c] = row[c] + (c == 0 ? dp[0] : Math.min(dp[c], dp[c - 1]));
        return dp[n - 1];
    }
}

Verdict: Simple rolling row.

Before you submit

Edge cases and common mistakes

Test these inputs

Single row or column
All zeros

Mistakes people make

Using Dijkstra (works, but DP is simpler and O(mn) for right/down moves).

Interview

Follow-up questions

When would you need Dijkstra instead?

Command Palette

The problem

Approaches

One-row DP

Edge cases and common mistakes

Follow-up questions