Minimum Path Sum

You get a grid of non-negative numbers with m rows and n columns.

Return the smallest sum of a path from the top-left cell to the bottom-right cell.

At each step, the path moves one cell right or one cell down. The sum includes every cell on the path, even the first and the last.

Example 1:

Input:
[
  [2,8,1],
  [3,4,6],
  [7,1,2]
]
Output: 12
Explanation: The path with the smallest sum is 2 → 3 → 4 → 1 → 2.
It goes down, right, down and right.
Its sum is 2 + 3 + 4 + 1 + 2 = 12.

Example 2:

Input:
[
  [5,0,9,1]
]
Output: 15
Explanation: There is only one row.
The only path goes right through every cell.
Its sum is 5 + 0 + 9 + 1 = 15.

Example 3:

Input:
[
  [1,4],
  [2,8],
  [6,0]
]
Output: 9
Explanation: The path with the smallest sum is 1 → 2 → 6 → 0.
It goes down the left column, then right.
Its sum is 1 + 2 + 6 + 0 = 9.

Constraints:

• 1 to 100 rows.
• 1 to 100 columns.
• Each number is from 0 to 99.