Array Matrix Breadth First Search
Intermediate Level

Implement the minimumPathSumMatrix method that returns the minimum path sum through the matrix.

The input matrix grid contains non-negative integer values, along with its rows and cols.

Your task is to move from the top-left cell to the bottom-right cell and return the minimum possible sum of values along the path.

At each step, you may move only right or down. 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[][]) = [[5]]
rows (int) = 1
cols (int) = 1
Return:
(int) 5

Use dynamic programming because the minimum cost to reach a cell depends only on the cell above it and the cell to its left.

For the first row, you can only come from the left. For the first column, you can only come from above. For every other cell, add the current cell value to the smaller of the two previous path sums.

The bottom-right cell will contain the minimum path sum for the whole matrix.

Pseudocode:

function minimumPathSumMatrix(grid, rows, cols):
    create dp matrix
    dp[0][0] = grid[0][0]
    for j from 1 to cols - 1:
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i from 1 to rows - 1:
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for i from 1 to rows - 1:
        for j from 1 to cols - 1:
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]
Run your code to see the result.