Intermediate Level
Implement the minimumPathSumGrid method that finds the minimum path sum from the top-left to the bottom-right of a grid.
The input contains a matrix grid with rows rows and cols columns. Your task is to find the minimum path sum from the top-left cell to the bottom-right cell.
From each cell, you may move only right or down. Add the values of all cells included in the path. For example, in [[1,3,1],[1,5,1],[4,2,1]], the minimum path sum is 7.
Example 1
Input
grid (int[][]) =
[[1,3,1],[1,5,1],[4,2,1]]rows (int) =
3cols (int) =
3Returns (int)
7Example 2
Input
grid (int[][]) =
[[1,2,3],[4,5,6]]rows (int) =
2cols (int) =
3Returns (int)
12Example 3
Input
grid (int[][]) =
[[9]]rows (int) =
1cols (int) =
1Returns (int)
9Use dynamic programming to store the smallest sum required to reach each cell.
The first cell starts with its own value. For every other cell, choose the cheaper path from the top cell or the left cell, then add the current cell value.
After filling the grid, the bottom-right cell contains the minimum path sum.
Pseudocode:
function minimumPathSumGrid(grid, rows, cols):
dp = 2D array of size rows x cols
for r from 0 to rows - 1:
for c from 0 to cols - 1:
if r == 0 and c == 0:
dp[r][c] = grid[r][c]
else:
bestPrevious = infinity
if r > 0:
bestPrevious = min(bestPrevious, dp[r - 1][c])
if c > 0:
bestPrevious = min(bestPrevious, dp[r][c - 1])
dp[r][c] = grid[r][c] + bestPrevious
return dp[rows - 1][cols - 1]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run