Minimum Path Sum: A Dynamic Programming Walkthrough

Minimum Path Sum is a dynamic programming problem interviewers use early in a loop because it's a clean test of fundamentals. Can you define a DP state that's actually self-contained? Can you identify the transitions without overthinking? Candidates who haven't internalized how to walk through a 2D DP table will fumble the indexing, miss the base cases, or jump straight to in-place optimization without justifying it. The interviewer is watching for clean reasoning, not cleverness.

Why does this question matter? Grid DP with monotonic movement shows up in image processing (seam carving cuts paths through pixel-cost grids the same way), route planning over weighted maps with directional constraints, manufacturing layout problems where parts flow through a grid of stations, and dynamic time warping in signal processing, which is essentially this exact recurrence in disguise.

Problem Statement

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

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

Return the minimum path sum.

Example: 

grid → [[1,3,1],[1,5,1],[4,2,1]]

answer → 7 (path: 1→3→1→1→1).

1. Clarify Requirements Before Jumping Into Code

Let's restate the problem in our own words and ask the kinds of questions that would affect our approach.

Input: a 2D grid of non-negative integers.

Output: an integer; the minimum sum along any valid path from top-left to bottom-right.

Details to clarify:

• Are negative values allowed? No, non-negative only, which simplifies things.

• Can we move diagonally or backward? No, right or down only.

• Are we guaranteed the grid has at least one cell? Yes.

• Do we return the sum or the actual path? Just the sum.

• Is it okay to modify the input grid in place? Worth asking - some interviewers care, some don't. Default to "I'll ask before doing it."

The thing to flag is that the movement is monotonic - right or down only, never up or left. That constraint is doing a lot of work. It means every cell can only be reached from two specific neighbors, which keeps the state space small.

2. Identify the Category of the Question

A few signals jump out:

• We're optimizing over paths in a grid.

• Movement is restricted to one of two directions at each step.

• The cost of a path is the sum of cell values along it.

• Paths overlap heavily - many paths to (i, j) share the same prefix.

That combination - a grid, monotonic movement, additive cost, and overlapping subproblems - is the fingerprint of grid DP. The state is almost always dp[i][j] representing some optimal value at cell (i, j), and the transition reads from a small number of neighboring cells. This is the same family as Unique Paths, Triangle, and Dungeon Game.

3. Brute Force Solution

As always, we start with the brute force solution. The most direct approach is to enumerate every valid path from (0, 0) to (m-1, n-1), sum the values along each, and return the minimum.

minPath(i, j):
    if (i, j) is bottom-right: return grid[i][j]
    if out of bounds: return infinity
    return grid[i][j] + min(minPath(i + 1, j), minPath(i, j + 1))

That's an exponential solution, closer to O(2^(m+n)), because at each cell we branch in two directions. The total number of paths in an m x n grid is C(m+n-2, m-1), which is combinatorially huge.

But the brute force does teach us one thing worth keeping: every path that reaches cell (i, j) must pass through either (i-1, j) (the cell above) or (i, j-1) (the cell to the left), because those are the only two cells from which we could have moved into (i, j). That fact is going to power the DP recurrence.

4. Brainstorm More Solutions

Step 1: How would we solve this manually?

The enumeration approach feels wrong, but it's worth asking why before abandoning it. What's actually expensive about it?

Let's count. From (0, 0) in our 3x3 grid, I can reach (2, 2) along multiple paths: right-right-down-down, right-down-right-down, down-right-down-right, and so on. Six paths total for a 3x3 grid.

Now look at any specific cell, say (1, 1). How many paths pass through (1, 1)? There are two ways to get there (right-down or down-right), times two ways to leave (right-then-down or down-then-right), giving us four paths. Every one of those paths recomputes the cost of reaching (1, 1) from scratch.

That's the waste. The cost to reach (1, 1) is the same regardless of which path I'm on. It's a fixed number that depends only on the cell, not on what comes after. But path enumeration recomputes it once per path that goes through it. As the grid grows, the number of paths through each cell explodes combinatorially, even though the answer at each cell is a single value.

So what if instead of computing all paths, we computed the minimum cost to reach each cell once, and looked it up afterward instead of recomputing it?

Concretely, suppose I knew the minimum cost to reach (2, 2) directly. That's my answer, no path enumeration required. To compute it, I'd need the minimum cost to reach the cells that lead into (2, 2) - namely (1, 2) and (2, 1). Those, in turn, depend on their predecessors. Every cell's answer depends on a small number of smaller cells' answers.

Looks like our logic is taking the shape of a DP solution.

Step 2: Define the state

Let's formalize our idea. We start by defining the state.

Let dp[i][j] be the minimum path sum to reach cell (i, j) from (0, 0). The answer we want is dp[m-1][n-1].

And how do we compute the value of dp[i][j]?

We know that every path that reaches (i, j) must have come either from above or from the left. The optimal path to (i, j) depends only on the optimal paths to those two predecessors.

In other words, to minimize our path to (i, j), we need to choose the best option between (i-1, j) (moving down), or (i, j-1) (moving right), and we pay a price of grid[i][j] to land on the current cell. So:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

But there's an edge case here: our predecessors might not exist. Let's handle that edge case next.

Step 3: Handle the boundaries

Let's handle the boundaries of our grid:

• Top row (i = 0): there's no cell above, so the only predecessor is (0, j-1). The cost to reach (0, j) is the sum of every cell from (0, 0) to (0, j).

• Left column (j = 0): there's no cell to the left, so the cost to reach (i, 0) is the cumulative sum down the first column.

• Top-left corner (0, 0): There are no predecessors at the starting cell. dp[0][0] = grid[0][0].

We can either special-case these inside the main loop or pre-fill them before the main loop runs. Pre-filling is cleaner because then the main loop becomes a uniform recurrence with no if statements:

dp[0][0] = grid[0][0]
for j from 1 to n-1: dp[0][j] = dp[0][j-1] + grid[0][j]
for i from 1 to m-1: dp[i][0] = dp[i-1][0] + grid[i][0]

This is the same kind of "pad the inputs to kill special cases" approach we've seen in other DP problems - initialize the boundary explicitly, and the body of the algorithm runs without exceptions.

We can walk through an example to confirm our reasoning. Let's verify on [[1,3,1],[1,5,1],[4,2,1]]:

Initialize by filling in the top row and left column:

1  4  5
2  .  .
6  .  .

Fill the interior with the recurrence dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]):

• dp[1][1] = 5 + min(4, 2) = 7

• dp[1][2] = 1 + min(5, 7) = 6

• dp[2][1] = 2 + min(7, 6) = 8

• dp[2][2] = 1 + min(6, 8) = 7

1  4  5
2  7  6
6  8  7

Final answer: dp[2][2] = 7. ✓

The state has two indices that together cover m × n distinct cells, and each cell does O(1) work to read its two neighbors and compute the min. So, by the "number of states × work per state" rule, the total runtime is O(m × n) with O(m × n) space.

Step 6: From bottom-up 2D DP to a rolling 1D array

Let's think through whether we can optimize on the 2D DP array.

Look at the recurrence:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). 

What rows does it actually read from? Just two: row i (the cell to the left) and row i-1 (the cell above). Row i-2 and everything older is dead weight. Once I've finished computing row i, I never look at row i-1 again, and rows below that are long gone.

That means I don't need a full m x n table. I only need two rows at a time: the previous row to read from, and the current row to fill in.

But can I push this even further? Think about what happens when I sweep across a single row left to right. To compute dp[i][j], I need dp[i-1][j] (the cell above) and dp[i][j-1] (the cell to my left in the current row). The cell to my left was just computed - it's already in the array. The cell above is in the previous row, but here's the trick: if I store both rows in the same 1D array of length n, then dp[j] already holds the value from the previous row at the start of the iteration, before I overwrite it. After I overwrite it, it holds the value for the current row. That's exactly what I need.

Our recurrence needs updating now that we're only tracking one row at a time:

dp[j] = grid[i][j] + min(dp[j], dp[j-1]). 

The dp[j] on the right side is the old value (from row i-1); the dp[j] on the left becomes the new value (for row i). It works because of the order I'm reading cells left to right.

This gives us the same O(m × n) time, but space drops to O(n). And critically, this version doesn't modify the input grid - it's the polite optimization that handles interviewers who say "don't touch the input." If they don't care about the input, we can push one step further.

Step 5: Explore in-place optimization

The bottom-up version uses a separate dp array of size m x n, which doubles the memory. But notice: when we compute dp[i][j], we read from dp[i-1][j] (the cell above in the same column) and dp[i][j-1] (the cell to the left in the same row). We don't read grid[i-1][j] or grid[i][j-1] ever again after we've finished computing their dp values.

That means we don't have to worry about maintaining their values. We can overwrite the input grid as we go. Each cell of grid gets replaced with the minimum path sum to reach it, and the rest of the algorithm reads those updated values. Same O(m × n) time, but space drops to O(1) extra, since we're just reusing what's already there.

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;

    // Top row: only one way to reach each cell
    for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];

    // Left column: only one way to reach each cell
    for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];

    // Interior: standard recurrence
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }

    return grid[m-1][n-1];
}

But be aware that this solution this modifies the input. In an interview, mention that out loud before doing it - some interviewers will care and some won't, but proactively addressing it shows good judgment. If they say "don't modify the input," fall back to using a separate dp array.

In summary, remember that this progression - brute-force recursion → 2D DP table → in-place / rolling array - is the same pattern that shows up in most grid DP problems. Each step removes a specific inefficiency. Showing that progression in an interview demonstrates that you understand why each optimization works, not just that it exists.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Brute-force recursion	O(2^(m+n))	O(m+n) stack	Never — but worth mentioning to frame the problem
Recursion + memoization	O(m × n)	O(m × n)	Easiest to write if I'm short on time and the recurrence is fresh
Bottom-up 2D DP	O(m × n)	O(m × n)	My default if the interviewer says "don't modify the input"
Rolling 1D array	O(m × n)	O(n)	A nice space optimization that preserves the input
In-place grid DP	O(m × n)	O(1) extra	The most efficient, but only if modifying the input is allowed

6. Pseudocode

m = number of rows, n = number of columns

# Initialize boundaries
for j from 1 to n - 1:
    grid[0][j] += grid[0][j - 1]
for i from 1 to m - 1:
    grid[i][0] += grid[i - 1][0]

# Fill the interior with the recurrence
for i from 1 to m - 1:
    for j from 1 to n - 1:
        grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

return grid[m - 1][n - 1]

7. Edge Cases

Things to verify before claiming we're done:

• Single-cell grid → no loops execute, return grid[0][0]. ✓

• Single row → only the top-row initialization loop runs, returns the row sum. ✓

• Single column → only the left-column initialization loop runs, returns the column sum. ✓

• All zeros → all paths have sum 0, returns 0. ✓

• Large dense grid → algorithm is O(m × n), handles it.

The boundary initialization handles the degenerate row/column cases without any extra logic. That's exactly why we pre-fill the boundaries instead of writing if (i == 0) checks inside the main loop.

8. Full Code

public class MinimumPathSum {

    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Top row: only reachable by moving right repeatedly
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        // Left column: only reachable by moving down repeatedly
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        // Interior: each cell is reached from above or from the left
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
}

9. Test the Code

System.out.println(minPathSum(new int[][]{
    {1, 3, 1},
    {1, 5, 1},
    {4, 2, 1}
}));  // 7

System.out.println(minPathSum(new int[][]{
    {1, 2, 3}
}));  // 6  (single row)

System.out.println(minPathSum(new int[][]{
    {1},
    {2},
    {3}
}));  // 6  (single column)

System.out.println(minPathSum(new int[][]{
    {0}
}));  // 0  (single cell)

System.out.println(minPathSum(new int[][]{
    {1, 2},
    {1, 1}
}));  // 3  (small 2x2)

These hit the meaningful cases: the canonical 3x3, a single row, a single column, the trivial single-cell grid, and a small 2x2 to spot-check the recurrence.

10. Key Lessons

• When movement is restricted (only right or down, only forward, only one direction at a time), the state space stays small because each cell only has a few possible predecessors. That's the structural property that makes grid DP work.

• Pre-fill the boundaries of a DP table before running the main loop. It turns the main loop into a uniform recurrence with no special cases, which is easier to write and easier to debug.

• "Cost to reach a cell" is usually a cleaner DP formulation than "cost to leave a cell," because the predecessors are determined by the movement rules, not by future choices.

• When the DP only reads from cells you've already computed and won't read again, in-place modification is a free space optimization. But always check whether the input is allowed to be modified before doing this.

• "number of states × work per state" is a good rule of thumb when thinking about how to derive time complexity.

Good Luck and Happy Coding!