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 {
public:
    int minPathSum(vector<vector<int>>& grid) {
        const int N = grid.size(), M = grid[0].size();
        vector<int> dp(M);
        
        // Initialize first row
        dp[0] = grid[0][0];
        for(int j = 1; j < M; j++) {
            dp[j] = dp[j-1] + grid[0][j];
        }
        
        // Process remaining rows
        for(int i = 1; i < N; i++) {
            dp[0] += grid[i][0];  // First column
            for(int j = 1; j < M; j++) {
                dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
            }
        }
        
        return dp[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