Array Dynamic Programming Matrix Tabulation
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) = 3
cols (int) = 3
Return:
(int) 7
Example 2
Input:
grid (int[][]) = [[1,2,3],[4,5,6]]
rows (int) = 2
cols (int) = 3
Return:
(int) 12
Example 3
Input:
grid (int[][]) = [[9]]
rows (int) = 1
cols (int) = 1
Return:
(int) 9

Use 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]
Run your code to see the result.