Minimum Path Sum
Problem 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.
Example 1:
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Output: 12
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The recursive approach is the most straightforward way to tackle this problem. Imagine that you need to move from the top-left to the bottom-right of the grid. At each cell (i, j), you have the choice to move either right to (i, j+1) or down to (i+1, j). The recursive solution explores both these paths and keeps track of the minimum sum encountered.
Code:
- Time Complexity: O(2^(m+n)) where m is the number of rows and n is the number of columns. This is because at each cell, you have two choices, so it's exponential.
- Space Complexity: O(m+n) for the recursion stack.
2. Dynamic Programming Approach (Bottom-Up)
Intuition:
This approach builds on the recursive solution but uses dynamic programming to avoid repeated calculations. The idea is to work backwards from the destination (bottom-right) cell and fill in a table with the minimum path sum to reach the bottom-right from any given cell.
Code:
- Time Complexity: O(2^(m+n)) where m is the number of rows and n is the number of columns. This is because at each cell, you have two choices, so it's exponential.
- Space Complexity: O(m+n) for the recursion stack.
3. Dynamic Programming Approach (In-Place)
Intuition:
We observe that to compute the value at any cell (i, j), we only need the values of the cell directly to the right (i, j+1) and the cell directly below (i+1, j) in the dp table. This allows us to actually use the input grid itself as our dp table to save space.
Code:
- Time Complexity: O(m*n) as we iterate over each cell exactly once.
- Space Complexity: O(1) since we use the input grid itself to store minimum path sums.