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.

Thinking Process

  1. 2D DP Pattern: Classic grid DP problem with optimal substructure
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
2D DP on grid 1 1 1 1 2 3 ← + ↑ cell from top + left neighbors

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Examples

Example 1:

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

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: The path is 1 → 2 → 3 → 6.

Constraints

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

Space Optimization

We can optimize space to O(min(m, n)) by using a 1D array:

class Solution:
    def minPathSum(self, grid):
        n = len(grid)
        m = len(grid[0])

        if n == 0 or m == 0:
            return 0

        dp = [[0] * m for _ in range(n)]

        dp[0][0] = grid[0][0]

        # first column
        for i in range(1, n):
            dp[i][0] = dp[i - 1][0] + grid[i][0]

        # first row
        for j in range(1, m):
            dp[0][j] = dp[0][j - 1] + grid[0][j]

        # fill rest
        for i in range(1, n):
            for j in range(1, m):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

        return dp[n - 1][m - 1]

Key Insight: We only need the previous row to compute the current row, so we can use a 1D array and update it row by row.

Common Mistakes

  1. Single cell: grid = [[5]] → return 5
  2. Single row: grid = [[1,2,3]] → return 6 (sum of row)
  3. Single column: grid = [[1],[2],[3]] → return 6 (sum of column)

  4. All zeros: grid = [[0,0],[0,0]] → return 0

  5. Wrong initialization: Not handling first row/column separately
  6. Index errors: Off-by-one errors in loops
  7. Wrong recurrence: Using max instead of min
  8. Base case errors: Not initializing dp[0][0] correctly
  9. Empty grid: Not handling empty grid case

Key Takeaways

  1. 2D DP Pattern: Classic grid DP problem with optimal substructure
  2. Base Cases: First row and column have only one path
  3. Recurrence: Choose minimum of top or left neighbor
  4. Space Optimization: Can reduce to O(min(m, n)) using rolling array

References

Template Reference