64. Minimum Path Sum - Detailed Explanation

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 such that the sum of all numbers along its path is minimized. You can only move either down or right at any step.

Example 1

• Input: grid =

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

• Output: 7
• Explanation: The path 1 → 3 → 1 → 1 → 1 gives a total sum of 7, which is the minimum possible.

Example 2

• Input: grid =

  [
    [1, 2, 3],
    [4, 5, 6]
  ]
  

• Output: 12
• Explanation: The path 1 → 2 → 3 → 6 (or 1 → 4 → 5 → 6) yields a sum of 12. In this grid, the optimal path totals 12.

Constraints:

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

Hints

1. Observation on Movements:
   Since you can only move right or down, every cell can be reached from its top or left cell (except the top row and the leftmost column). This dependency suggests that dynamic programming can be applied.

2. Overlapping Subproblems:
   Notice that to compute the minimum path sum to a cell, you only need the results from the cell immediately above and the one to the left. This overlapping nature of subproblems indicates that a bottom-up dynamic programming approach is efficient.

Approaches

Approach 1: Dynamic Programming

Explanation

The idea is to define a 2D DP table where each dp[i][j] represents the minimum path sum from the start (grid[0][0]) to cell (i, j). The recurrence relation is:

• Base Case:
  dp[0][0] = grid[0][0]

• First Row:
  For j > 0, dp[0][j] = dp[0][j-1] + grid[0][j]
  (Since you can only come from the left)

• First Column:
  For i > 0, dp[i][0] = dp[i-1][0] + grid[i][0]
  (Since you can only come from above)

• General Case:
  For other cells, dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
  (Choose the smaller path sum from above or from the left)

Finally, dp[m-1][n-1] gives the minimum path sum for the entire grid.

Complexity Analysis

• Time Complexity: O(m × n) because every cell is visited once.
• Space Complexity: O(m × n) if we use a separate DP table; however, it is possible to reduce space usage to O(n) by modifying the grid in place.

Approach 2: Recursive with Memoization

An alternative is to use recursion with memoization. This involves defining a recursive function that computes the minimum path to a given cell and caches results for overlapping subproblems. Although this approach is effective, it uses extra overhead, and the iterative dynamic programming solution is more straightforward.

Code Solutions

Python Implementation

Step-by-Step Walkthrough and Visual Example

Consider Example 1 with the grid:

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

1. Initialization:
   Create a DP table of the same size, where dp[0][0] = 1 (the first cell).

2. Filling the First Row:

   • dp[0][1] = dp[0][0] + 3 = 4
   • dp[0][2] = dp[0][1] + 1 = 5

3. Filling the First Column:

   • dp[1][0] = dp[0][0] + 1 = 2
   • dp[2][0] = dp[1][0] + 4 = 6

4. Filling the Rest:

   • For dp[1][1]: Choose the minimum of dp[0][1] (4) and dp[1][0] (2), add current grid[1][1] (5) → dp[1][1] = 5 + min(4, 2) = 7
   • For dp[1][2]: Min of dp[0][2] (5) and dp[1][1] (7), add grid[1][2] (1) → dp[1][2] = 1 + min(5, 7) = 6
   • For dp[2][1]: Min of dp[1][1] (7) and dp[2][0] (6), add grid[2][1] (2) → dp[2][1] = 2 + min(7, 6) = 8
   • For dp[2][2]: Min of dp[1][2] (6) and dp[2][1] (8), add grid[2][2] (1) → dp[2][2] = 1 + min(6, 8) = 7

The final dp table looks like:

[ [1, 4, 5],
  [2, 7, 6],
  [6, 8, 7] ]

The answer is dp[2][2] which is 7.

Common Mistakes

• Mismanaging the Base Cases:
  Be sure to correctly initialize the first row and first column since they only have one possible path.

• Indexing Errors:
  Care must be taken when filling the DP table. Off-by-one errors are common when iterating over matrix indices.

• Overcomplicating the Problem:
  Remember that you only need to consider moves right and down. There is no need to look upward or left as each cell’s solution is built from previous computations.

Alternative Variations

• Minimum Cost to Make at Least One Valid Path in a Grid

• Maximum Area Rectangle With Point Constraints I