Approach Summary
In-place DP: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Bottom-right cell holds the answer.
How to Recognize This Pattern
- "Minimum cost path in grid — only right or down moves"
- Standard 2D DP — can reuse input grid in-place
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(1)
Tags
Array Dynamic Programming Matrix