Maximum Path Sum in the matrix

The basic approach is that we are going to explore all possible paths recursively from the first row for each cell and return the maximum sum among all paths. Steps are as follows:

1. Start exploring the path from each cell of the first row.
2. And the path can end at any cell of the last row.
3. If any move gets out of the boundary of the given matrix, then we return negative infinity, i.e. INT_MIN, because we do not want to consider that move in our path.
4. Now we can move to follow three cells from the cell (row, col)
   • Down move : (row+1, col)
   • Down left diagonal : (row+1, col-1)
   • Down right diagonal : (row+1, col+1)
5. Now among the above three paths, which path has the maximum sum that will be the maximum path sum from (row, col) to any cell of the last node. So return the sum of the current cell and maximum path what we got from above three paths.
6. So above steps can be recursively defined as:

getMaxPathSum(row,col)=matrix[row][col]+max(getMaxPathSum(row+1,col),*max(getMaxPathSum(row+1,col+1),getMaxPathSum(row+1,col-1))

If we draw the recursion tree for the recursive solution of Approach-1, we can observe that there is a lot of overlapping subproblems, there is only N*M distinct recursive call. Since the problem has overlapping subproblems so we can solve it more efficiently using memoization.

Let’s say we have “dp” such that:

Dp[row][col], will store the maximum sum which will path from (row, col) to any cell of the last row including (row, col) cells.

Before calling the function for any valid (row, col), we will first check whether we have already a solution corresponding to the (row, col), if we have already a solution then we return the solution else we will solve it with following steps :

1. We can move to follow three cells from a cell (row, col)
   1. Down move : (row+1,col)
   2. Down left diagonal : (row+1 , col-1)
   3. Down right diagonal : (row+1, col+1)
2. Now among the above three paths, which path has the maximum sum that will be the maximum path sum from (row, col). So return the sum of the current cell and maximum path what we got from above three paths.
3. So the above steps can be recursively defined as:

getMaxPathSum(row,col)=matrix[row][col]+max(getMaxPathSum(row+1,col),max(getMaxPathSum(row+1,col+1), getMaxPathSum(row+1, col-1) )

   4. And finally, before returning the answer, we will save it in “dp” for later use.

We are given an N*M matrix. Our idea behind this approach is while traversing in the given matrix, and we will keep updating the matrix with the best sum path till now. That means, we are going to the next row after completing the current row, So for each cell, all the cells from where we can reach here already contain the best path sum from any cell of the first row to that cell. Let’s say we are at (row, col), So there is only three way to reach (row, call):

1. From up:(row-1, col)
2. From up left diagonal:(row-1,col-1)
3. From upright diagonal:(row-1,col+1)

 So, matrix[row][col] will be,

matrix[row][col] = matrix[row][col] + max(matrix[row - 1][col], max(matrix[row - 1][max(0, col - 1)], matrix[row - 1][min(m-1, col + 1)]));

Where ‘M’ is the number of columns in the given matrix.

Once we have updated the “matrix” then each cell of the matrix (row, col)  will represent the maximum path sum for any cell from the first row to current (row, col) cell. So we will traverse in the last row and find the maximum value that will be the maximum path sum from any cell of the first row to any cell of the last row.