137. Minimum Path Sum
Travel from the upper-left cell to the lower-right cell, moving only right or down. Add the costs of every visited cell and choose the path with the smallest sum.
Include both the starting cell and ending cell in the cost. The goal is minimum summed cost, not the smallest number of moves.
Example 1
Input
grid=[[1,3,1],[1,5,1],[4,2,1]]
Output
7
Explanation: One minimum path follows the top row then the final column: 1+3+1+1+1.
Example 2
Input
grid=[[1,2,3],[4,5,6]]
Output
12
Explanation: Right,right,down costs 1+2+3+6.
Example 3
Input
grid=[[2147483647,2147483647],[2147483647,2147483647]]
Output
6442450941
Explanation: Every route uses three cells; int accumulation would overflow.
Example 4
Input
grid=[]
Output
0
Explanation: The empty-grid convention is not a path witness.
Constraints
0 <= grid.length <= 1050 <= total grid cells <= 1050 <= grid[r][c] <= 231 - 1- All rows have equal length and are non-null.
Hints
Hint 1
What are the only two cells that can immediately precede an interior destination?
Hint 2
Write a minimum cost inclusive of the current cell, then initialize the unique boundary routes.
Hint 3
In one row, compare old dp[c] with new dp[c−1] and add the current cost as long.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Optimal costs accumulate across rows
[[1,3,1],[1,5,1],[4,2,1]]
7