MediumNeetCode150ArrayDynamic ProgrammingMatrix
Minimum Path Sum
Find path with minimum sum.
Examples
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
1->3->1->1->1 = 7.
Constraints
- •
m == grid.length - •
n == grid[0].length - •
1 <= m,n <= 200 - •
0 <= grid[i][j] <= 200
Approaches
DFS all paths.
CodeT: O(2^(m+n)) | S: O(m+n) stack
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
CodeT: O(m*n) | S: O(m*n)
Modify grid.
CodeT: O(m*n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^(m+n)) | O(m+n) stack | DFS all paths. |
| DP 2D | O(m*n) | O(m*n) | dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). |
| DP In Place | O(m*n) | O(1) | Modify grid. |
Recursion
T: O(2^(m+n))S: O(m+n) stack
DFS all paths.
DP 2D
T: O(m*n)S: O(m*n)
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
DP In Place
T: O(m*n)S: O(1)
Modify grid.
Common Mistakes
Not handling first row/col
Wrong min calculation
Off-by-one