1. Problem Statement (Simple Explanation)
You’re given an m x n grid of non-negative integers.
Start at top-left: (0, 0)
End at bottom-right: (m-1, n-1)
You can move only right or down.
You must find a path from start to end with the minimum possible sum of values on the path and return that sum.
2. Examples
Example 1:
Input:
grid = [
[1,3,1],
[1,5,1],
[4,2,1]
]
Minimum path:
1 → 3 → 1 → 1 → 1
(Right, Right, Down, Down or some equivalent variant)
Sum = 1 + 3 + 1 + 1 + 1 = 7
Output: 7
Example 2:
Input:
grid = [
[1,2,3],
[4,5,6]
]
Minimum path:
1 → 2 → 3 → 6
Sum = 1 + 2 + 3 + 6 = 12
Output: 12
3. Approach – Dynamic Programming (O(m·n))
Let dp[i][j] be the minimum path sum to reach cell (i, j) from (0, 0).
Transition:
To reach (i, j), you can come from:
(i-1, j) (down from above)
(i, j-1) (right from left)
So:
dp[i][j] = grid[i][j] + min(
dp[i-1][j] (if i > 0),
dp[i][j-1] (if j > 0)
)
Base cases:
Start cell:
dp[0][0] = grid[0][0]
First row (i = 0, j > 0):
dp[0][j] = grid[0][j] + dp[0][j-1]
First column (j = 0, i > 0):
dp[i][0] = grid[i][0] + dp[i-1][0]
We can implement:
Either in a separate dp array.
Or in-place by updating grid itself.
In-place DP (using grid as dp):
We can re-use grid[i][j] to store dp[i][j]:
Update first row:
for j in 1..n-1:
grid[0][j] += grid[0][j-1]
Update first column:
for i in 1..m-1:
grid[i][0] += grid[i-1][0]
For all other cells:
for i in 1..m-1:
for j in 1..n-1:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
Answer is grid[m-1][n-1].
Pseudo-code:
Let m = rows, n = cols:
Time: O(m⋅n)
Space: O(1) extra if done in-place, or O(m⋅n) if using separate dp.
4. Java code
7. Python code
8. JavaScript code
Comments
Post a Comment