0064. Minimum Path Sum¶

Table of Contents¶

1. Problem
2. Problem Breakdown
3. Approach 1: Top-Down DP (Memoization)
4. Approach 2: Bottom-Up DP (2D)
5. Approach 3: Bottom-Up DP (1D, Space Optimized)
6. Approach 4: In-Place DP
7. Complexity Comparison
8. Edge Cases
9. Common Mistakes
10. Related Problems
11. Visual Animation

Problem¶

Leetcode	64. Minimum Path Sum
Difficulty	Medium
Tags	Array, Dynamic Programming, Matrix

Description¶

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

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

Examples¶

Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: 1 → 2 → 3 → 6 sums to 12.

Constraints¶

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

Problem Breakdown¶

1. What is being asked?¶

Find a path from (0, 0) to (m-1, n-1) moving only right or down, with minimum total sum of cell values.

2. What is the input?¶

3. What is the output?¶

A single integer: minimum sum among all valid paths.

4. Constraints analysis¶

5. Step-by-step example analysis¶

Example 1: [[1,3,1],[1,5,1],[4,2,1]]¶

grid:        DP table:
1 3 1         1 4 5
1 5 1   →     2 7 6
4 2 1         6 8 7

dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
First row: cumulative sum from left.
First col: cumulative sum from top.

Answer: dp[2][2] = 7.
Path: 1 → 3 → 1 → 1 → 1.

6. Key Observations¶

1. Recurrence -- dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
2. Border init -- First row sums left-to-right; first column sums top-to-bottom.
3. 1D rolling array -- Only need previous row. dp[c] = grid[r][c] + min(dp[c], dp[c-1]).
4. In-place -- We can mutate grid itself.

7. Pattern identification¶

Chosen pattern: Bottom-Up DP (1D).

Approach 1: Top-Down DP (Memoization)¶

Idea¶

f(r, c) = min sum from (0,0) to (r,c). Recurse on the predecessors with memoization.

Complexity¶

Implementation¶

Python¶

class Solution:
    def minPathSumMemo(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def f(r: int, c: int) -> int:
            if r == 0 and c == 0: return grid[0][0]
            if r < 0 or c < 0: return float('inf')
            return grid[r][c] + min(f(r - 1, c), f(r, c - 1))
        return f(m - 1, n - 1)

Approach 2: Bottom-Up DP (2D)¶

Algorithm¶

1. dp[0][0] = grid[0][0].
2. Fill first row: dp[0][c] = dp[0][c-1] + grid[0][c].
3. Fill first column: dp[r][0] = dp[r-1][0] + grid[r][0].
4. For r = 1..m-1, c = 1..n-1: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).

Complexity¶

Implementation¶

Go¶

func minPathSum2D(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)
    for i := range dp { dp[i] = make([]int, n) }
    dp[0][0] = grid[0][0]
    for c := 1; c < n; c++ { dp[0][c] = dp[0][c-1] + grid[0][c] }
    for r := 1; r < m; r++ { dp[r][0] = dp[r-1][0] + grid[r][0] }
    for r := 1; r < m; r++ {
        for c := 1; c < n; c++ {
            up, left := dp[r-1][c], dp[r][c-1]
            if up < left {
                dp[r][c] = grid[r][c] + up
            } else {
                dp[r][c] = grid[r][c] + left
            }
        }
    }
    return dp[m-1][n-1]
}

Approach 3: Bottom-Up DP (1D, Space Optimized)¶

Algorithm¶

1. dp = [0] * n. dp[0] = grid[0][0]. Fill first row prefix.
2. For each r = 1..m-1:
3. dp[0] += grid[r][0].
4. For c = 1..n-1: dp[c] = grid[r][c] + min(dp[c], dp[c-1]).

Complexity¶

Implementation¶

Go¶

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([]int, n)
    dp[0] = grid[0][0]
    for c := 1; c < n; c++ { dp[c] = dp[c-1] + grid[0][c] }
    for r := 1; r < m; r++ {
        dp[0] += grid[r][0]
        for c := 1; c < n; c++ {
            if dp[c] < dp[c-1] {
                dp[c] = grid[r][c] + dp[c]
            } else {
                dp[c] = grid[r][c] + dp[c-1]
            }
        }
    }
    return dp[n-1]
}

Java¶

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for (int c = 1; c < n; c++) dp[c] = dp[c - 1] + grid[0][c];
        for (int r = 1; r < m; r++) {
            dp[0] += grid[r][0];
            for (int c = 1; c < n; c++) {
                dp[c] = grid[r][c] + Math.min(dp[c], dp[c - 1]);
            }
        }
        return dp[n - 1];
    }
}

Python¶

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [0] * n
        dp[0] = grid[0][0]
        for c in range(1, n):
            dp[c] = dp[c - 1] + grid[0][c]
        for r in range(1, m):
            dp[0] += grid[r][0]
            for c in range(1, n):
                dp[c] = grid[r][c] + min(dp[c], dp[c - 1])
        return dp[n - 1]

Dry Run¶

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

Init: dp = [1, 4, 5]   # cumulative on row 0

Row 1: dp[0] = 1 + 1 = 2
  c=1: dp[1] = 5 + min(4, 2) = 5 + 2 = 7
  c=2: dp[2] = 1 + min(5, 7) = 1 + 5 = 6
  dp = [2, 7, 6]

Row 2: dp[0] = 2 + 4 = 6
  c=1: dp[1] = 2 + min(7, 6) = 2 + 6 = 8
  c=2: dp[2] = 1 + min(6, 8) = 1 + 6 = 7
  dp = [6, 8, 7]

Return dp[2] = 7.

Approach 4: In-Place DP¶

Idea¶

Mutate grid[r][c] to hold the min sum to reach it. Same recurrence with no extra allocation.

Implementation¶

Python¶

class Solution:
    def minPathSumInPlace(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for c in range(1, n): grid[0][c] += grid[0][c - 1]
        for r in range(1, m): grid[r][0] += grid[r - 1][0]
        for r in range(1, m):
            for c in range(1, n):
                grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])
        return grid[m - 1][n - 1]

Complexity Comparison¶

Which solution to choose?¶

• In an interview: Approach 3
• In production: Approach 3 (or 4 if mutation acceptable)
• On Leetcode: Approach 3

Edge Cases¶

Common Mistakes¶

Mistake 1: Greedy along the path¶

# WRONG — at each cell pick the smaller of right/down value
# This is myopic and can miss the global minimum

# CORRECT — DP from end backward, or from start forward, considering all paths

Reason: Greedy ignores future costs. A small local saving may lead to a large later cost.

Mistake 2: Forgetting first-column update in 1D form¶

# WRONG — forgets dp[0] += grid[r][0]
for r in range(1, m):
    for c in range(1, n):
        dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

# CORRECT
for r in range(1, m):
    dp[0] += grid[r][0]
    for c in range(1, n):
        dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

Reason: Without updating dp[0], the column-0 contribution stays at row 0, giving wrong totals.

Mistake 3: Using += instead of =¶

# WRONG — dp[c] += min(...) double-counts the previous row's contribution
dp[c] += grid[r][c] + min(dp[c], dp[c - 1])

# CORRECT
dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

Reason: The recurrence already includes the previous row's value via dp[c] on the right side; assignment must replace the old value.

Related Problems¶

#	Problem	Difficulty	Similarity
1	62. Unique Paths	Medium	Count paths instead of min sum
2	63. Unique Paths II	Medium	Same with obstacles
3	120. Triangle	Medium	Min path on triangle
4	931. Minimum Falling Path Sum	Medium	Min path with diagonal moves

Visual Animation¶

Interactive animation: animation.html

The animation includes: - Grid coloring by current DP value - Highlight current cell + its predecessors (above / left) - Trace the optimal path from end back to start - Toggle 2D vs 1D view