Array Dynamic Programming Matrix Tabulation
Intermediate Level

Implement the maximumPathSumGrid method that finds the maximum 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 maximum 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 maximum path sum is 12.

Example 1
Input:
grid (int[][]) = [[1,3,1],[1,5,1],[4,2,1]]
rows (int) = 3
cols (int) = 3
Return:
(int) 12
Example 2
Input:
grid (int[][]) = [[5]]
rows (int) = 1
cols (int) = 1
Return:
(int) 5
Example 3
Input:
grid (int[][]) = [[1,2,3],[4,5,6]]
rows (int) = 2
cols (int) = 3
Return:
(int) 16

Use dynamic programming to store the best sum that can reach each cell.

The first cell starts with its own value. For every other cell, you can come either from the top cell or from the left cell. To maximize the path sum, add the current cell value to the larger of those two previous sums.

The value stored at the bottom-right cell is the maximum path sum.

Pseudocode:

function maximumPathSumGrid(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 = negative infinity
                if r > 0:
                    bestPrevious = max(bestPrevious, dp[r - 1][c])
                if c > 0:
                    bestPrevious = max(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.