Minimum Path Sum — Grid DP That Minimizes Cost Instead of Counting Paths

Problem Statement#

Given an m x n grid filled with non-negative integers, find a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) that minimizes the sum of all numbers along its path. You can only move right or down.

Constraints:

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

Example 1:

Input:  grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 -> 3 -> 1 -> 1 -> 1 sums to 7.

Example 2:

Input:  grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: The path 1 -> 2 -> 3 -> 6 sums to 12.

Example 3:

Input:  grid = [[5]]
Output: 5
Explanation: Single-cell grid — the only path is the cell itself.

Why This Problem Matters#

Minimum Path Sum is the cost-minimization twin of Unique Paths. Where LC 62 counts the number of paths, LC 64 minimizes the total cost. Both share identical movement rules (right or down only) and identical DP structure — the only change is the operation: addition of counts becomes a minimum of costs.

Amazon, Google, and Microsoft include this problem in FAANG interview rounds because it tests whether candidates can adapt a familiar pattern to a new objective. It also introduces the idea of accumulating costs along a path — a concept that generalizes to Dungeon Game (LC 174), Triangle (LC 120), and countless competitive programming problems.

The in-place variant (mutating the grid directly) teaches space awareness. The 1D rolling array variant is the interview gold standard. Both are worth knowing.

The Core Insight#

Define dp[i][j] as the minimum path sum to reach cell (i, j) from (0, 0).

State: The minimum cost to reach (i, j) is the cell's own value plus the minimum cost of reaching either the cell above it (i-1, j) or the cell to its left (i, j-1). Take whichever is cheaper.

Base cases:

• dp[0][0] = grid[0][0] (start cell — no choice).
• First row: dp[0][j] = dp[0][j-1] + grid[0][j] — can only arrive from the left.
• First column: dp[i][0] = dp[i-1][0] + grid[i][0] — can only arrive from above.

Recurrence:

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

Answer: dp[m-1][n-1]

The key structural insight: unlike Unique Paths where you add two contributions (both directions contribute independently), here you take the minimum (only the cheaper direction matters). This is the classic shift from counting to optimizing.

Building the DP Solution#

Step 1 — Recursive (exponential):

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    def rec(i, j):
        if i == 0 and j == 0:
            return grid[0][0]
        if i == 0:
            return rec(0, j-1) + grid[0][j]
        if j == 0:
            return rec(i-1, 0) + grid[i][0]
        return grid[i][j] + min(rec(i-1, j), rec(i, j-1))
    return rec(m-1, n-1)

Exponential recomputation — only useful to see the recurrence structure.

Step 2 — Memoized recursion:

from functools import lru_cache
 
def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    @lru_cache(None)
    def dp(i, j):
        if i == 0 and j == 0:
            return grid[0][0]
        if i == 0:
            return dp(0, j-1) + grid[0][j]
        if j == 0:
            return dp(i-1, 0) + grid[i][0]
        return grid[i][j] + min(dp(i-1, j), dp(i, j-1))
    return dp(m-1, n-1)

O(m * n) time and space. Correct but uses call stack.

Step 3 — Bottom-up 2D tabulation:

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

Step 4 — In-place (O(1) space, mutates grid): Write results back into grid itself. Same recurrence, no extra array.

Visual Dry Run#

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

Initialized borders:

• Row 0: dp[0][1] = 1+3=4, dp[0][2] = 4+1=5
• Col 0: dp[1][0] = 1+1=2, dp[2][0] = 2+4=6

Fill interior:

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

Final DP table:

The optimal path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) = 1+3+1+1+1 = 7.

Optimized Solution#

Python#

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
 
        # 1D rolling array: dp[j] = min path sum to current row, column j
        dp = [float('inf')] * n
        dp[0] = 0  # will be overwritten with grid[0][0] on first row pass
 
        for i in range(m):
            # Left boundary: can only come from above
            dp[0] += grid[i][0]
            for j in range(1, n):
                # min of coming from above (dp[j]) or from left (dp[j-1])
                dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
 
        return dp[n - 1]

JavaScript#

var minPathSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
 
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;
 
    for (let i = 0; i < m; i++) {
        dp[0] += grid[i][0];
        for (let j = 1; j < n; j++) {
            dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
        }
    }
 
    return dp[n - 1];
};

Complexity Analysis#

Common Mistakes#

1. Taking the sum of both neighbors instead of the minimum. This is the most common mistake for candidates transitioning from Unique Paths. In counting problems you sum contributions; in optimization problems you take the minimum (or maximum). Confirm the objective before writing the recurrence.

2. Forgetting to initialize the first row and first column correctly. The first row accumulates costs from the left only; the first column accumulates from above only. Using min(dp[i-1][j], dp[i][j-1]) when either i == 0 or j == 0 would read uninitialized values.

3. Mutating the grid without informing the interviewer. In-place DP is space-efficient but destroys the caller's data. Always ask: "Is it acceptable to modify the input array?" before proceeding.

4. Mishandling the 1D rolling array initialization. Setting dp[0] = 0 and then adding grid[i][0] on each row iteration accumulates the first column correctly. Setting dp[0] = grid[0][0] initially and adding from row 1 onward also works — but mixing the two approaches causes an off-by-one error.

5. Not verifying the answer on a 1x1 grid. A single-cell grid [[5]] must return 5. Many implementations fail here if they special-case borders incorrectly.

Interview Tips#

• State the recurrence difference explicitly: "Instead of summing two path counts as in Unique Paths, we take the minimum of two path costs."
• Narrate the border initialization: "First row accumulates left-to-right since you can only arrive from the left. First column accumulates top-to-bottom for the same reason."
• Offer two space complexities: O(m * n) for the full table (easy to debug), O(n) for the 1D rolling array (interview optimal).
• If asked about in-place: "We can write DP values back into the grid for O(1) space, but that mutates the input — I'd prefer to clarify with the interviewer first."
• Path reconstruction: "To recover the actual path, I'd save the full 2D table and trace back from (m-1, n-1) by always moving toward the cheaper neighbor."

Follow-up Questions#

Q: How do you reconstruct the actual minimum-cost path? Save the full 2D DP table. Backtrack from (m-1, n-1): at each cell, move toward whichever of the cell above or the cell to the left has a smaller dp value. This gives the path in O(m+n) time.

Q: What if the grid has negative numbers? (See LC 174 Dungeon Game) Negative values mean healing rooms. You need to track minimum health, not minimum cost — which requires a reverse DP from the destination. See Dungeon Game.

Q: What if you can also move up or left? The 2D DP recurrence breaks due to circular dependencies. Use Dijkstra's shortest path algorithm, treating each cell as a graph node with weighted edges.

Q: What if multiple start/end points exist? Initialize a multi-source DP: set dp[i][j] = grid[i][j] for all start cells and propagate. Or run one pass per start and take the global minimum.

Q: How would you handle very large grids (m, n up to 10^5)? The O(m * n) DP is infeasible at that scale. For DAG-structured grids (right/down only), divide-and-conquer or segment-tree optimizations can reduce certain variants, but standard interview scope is m, n up to a few hundred.

Key Takeaways#

• dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) is the cost-minimization twin of the Unique Paths counting recurrence — the structure is identical, only the operation changes.
• Border initialization is the critical step: first row accumulates left-to-right, first column accumulates top-to-bottom.
• The 1D rolling array works because only the current and previous row values are needed at each step — update dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
• In-place modification achieves O(1) space but mutates the input — always discuss this trade-off in an interview.
• This recurrence generalizes to Triangle (bottom-up), Dungeon Game (reverse DP), and Minimum Falling Path Sum (flexible column entry) — the same "add cell cost, take optimal direction" pattern repeats across all of them.
• Amazon and Google ask this as a direct follow-up to Unique Paths: "What if each cell has a cost?" Know it cold.