Given a non-empty grid of non-negative integers, return the minimum sum of values along a path from the top-left cell to the bottom-right cell when you may only move right or down. Pattern focus: Min path sum. Build the answer cell by cell using optimal substructure.
grid is a non-empty matrix of non-negative integers
minimum path sum
Example 1:
Input:
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output:
7
Explanation:
The minimum path cost is 7 via 1 → 3 → 1 → 1 → 1.
Example 2:
Input:
grid = [[1,2,3],[4,5,6]]
Output:
12
Explanation:
The cheapest route is 1 → 2 → 3 → 6 for a total of 12.
Example 3:
Input:
grid = [[5]]
Output:
5
Explanation:
A single-cell grid returns that cell value.