Problem Statement
Given an m x n grid filled with non-negative numbers, find a path from the top-left to the bottom-right that minimizes the sum of all numbers along its path.
Example Inputs and Outputs
-
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 → 3 → 1 → 1 → 1 minimizes the sum.
-
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
For the first example input grid = [[1,3,1],[1,5,1],[4,2,1]]:
The minimum path (highlighted with brackets) would be:
Which gives us: 1 + 3 + 1 + 1 + 1 = 7
For the second example grid = [[1,2,3],[4,5,6]]:
The minimum path (highlighted with brackets) would be:
Which gives us: 1 + 2 + 3 + 6 = 12
Key Points:
- You can only move right (→) or down (↓)
- You must start at the top-left corner
- You must end at the bottom-right corner
- The goal is to find the path with the smallest sum of numbers
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
Approach
a. Dynamic Programming (Recursive with Memoization)
Steps
- Create a recursive function
rec(r, c, grid, dp) that computes the minimum path sum to cell (r, c):
- If the robot moves out of bounds (
r < 0 || c < 0), return a large value (1e7).
- If the robot reaches the top-left corner (
r === 0 && c === 0), return the value of grid[r][c].
- Check the memoization table
dp to avoid redundant computations.
- Transition to the current cell
(r, c) from:
- The cell above
(r-1, c)
- The cell to the left
(r, c-1)
- Return and memoize the minimum value of the two transitions plus the current cell value.
- Call
rec(m-1, n-1, grid, dp) to compute the result.
Time & Space Complexity
- Time Complexity:
O(m * n) since each cell is computed once.
- Space Complexity:
O(m * n) for the memoization table.
Code Snippet
Dry Run
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Initialization:
dp = [[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
Recursive Calls:
- Start at
(2, 2):
- From
(1, 2) → dp[1][2]
- From
(2, 1) → dp[2][1]
- Compute recursively for
(1, 2) and (2, 1) until reaching (0, 0).
Final Memoization Table:
Output: 7
Complexity Analysis
Conclusion
This guide demonstrates a dynamic programming approach to solving the minimum path sum problem. By memoizing intermediate results, we avoid redundant computations and ensure efficiency for large grids. This approach highlights the importance of leveraging DP to optimize recursive solutions.