Given an n x m matrix of integers, return the maximum path sum from the first row to the last row when each move may go straight down, down-left, or down-right. Pattern focus: Direction variants. This is the maximum-sum mirror image of the falling path problems.
matrix is an n x m integer matrix
maximum path sum from top row to bottom row
Example 1:
Input:
matrix = [[10,10,2,0,20,4],[1,0,0,30,2,5],[0,10,4,0,2,0],[1,0,2,20,0,4]]
Output:
74
Explanation:
The maximum path sum from top to bottom is 74.
Example 2:
Input:
matrix = [[3,1,7,4],[2,4,6,8],[5,9,3,2]]
Output:
22
Explanation:
The best path sums to 22.
Example 3:
Input:
matrix = [[5]]
Output:
5
Explanation:
A single-cell matrix returns 5.