Find the optimal path through a grid using dynamic programming to minimize the sum of values along the path
Path: 1→3→1→1→1
Path: 1→2→3→6
Create a 1D array dp[] of size n and initialize the first row with cumulative sums.
For each row, update dp[0] by adding the current cell value to represent the cumulative sum down the first column.
For each cell, choose the minimum between coming from top (dp[j]) or left (dp[j-1]) and add current cell value.
Process each row left to right, updating dp[] array in-place with optimal path sums.
The last element dp[n-1] contains the minimum path sum from top-left to bottom-right.
Original grid with values
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
"""
Find minimum path sum from top-left to bottom-right.
Time: O(m*n), Space: O(n) - optimized 1D DP
"""
m, n = len(grid), len(grid[0])
# Edge case optimization
if m == 1 and n == 1:
return grid[0][0]
# Initialize 1D DP array with first row
dp = [0] * n
dp[0] = grid[0][0]
# Fill first row with cumulative sums
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
# Process remaining rows
for i in range(1, m):
# Update first column (can only come from above)
dp[0] += grid[i][0]
# Update remaining columns (min of top or left)
for j in range(1, n):
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
return dp[n - 1]Create 1D DP array and fill the first row with cumulative sums. This represents the minimum cost to reach each position in the first row.
For each subsequent row, update the DP array by choosing the minimum cost path (from top or left) and adding the current cell value.
After processing all rows, dp[n-1] contains the minimum path sum from the top-left to bottom-right corner of the grid.
| Approach | Time | Space | Pros | Cons |
|---|---|---|---|---|
| 1D DP (Optimal) | O(m×n) | O(n) | Memory efficient, cache-friendly | Slightly complex logic |
| 2D DP | O(m×n) | O(m×n) | Intuitive, easy to understand | High memory usage |
| In-place DP | O(m×n) | O(1) | Minimal memory | Destroys input, not always allowed |
| Recursive + Memo | O(m×n) | O(m×n) | Natural problem mapping | Stack overflow risk, slower |
Achieves optimal O(m×n) time complexity while minimizing space usage to O(n)
Sequential memory access pattern improves cache performance on modern processors
Perfect balance between time efficiency, space optimization, and code maintainability