Given a weighted grid, return the minimum cost to travel from the top-left cell to the bottom-right cell when you may move right, down, or diagonally down-right. Pattern focus: Min path sum. Extend the standard grid DP recurrence to support diagonal transitions.
grid is a matrix of positive weights
minimum travel cost
Example 1:
Input:
grid = [[1,2,3],[4,8,2],[1,5,3]]
Output:
8
Explanation:
Allowing diagonal movement lowers the total cost to 8.
Example 2:
Input:
grid = [[1,2,1],[4,3,2],[7,1,1]]
Output:
5
Explanation:
The minimum cost path has total cost 5.
Example 3:
Input:
grid = [[5]]
Output:
5
Explanation:
The answer for a 1x1 grid is the cell value itself.