Minimum Path Sum
Given an m x n grid filled with non-negative integers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of the numbers along the path. You can only move right or down at each step.
The starting cell and the ending cell both count toward the sum.
Input & Output
Input
grid — the grid of non-negative cell costs
Output
the smallest sum of cell values along any right/down path from the top-left cell to the bottom-right cell
Example
Input
grid = [[1,2,3],[4,5,6]]
Output
12
Explanation
Three paths exist. Staying on the top row as long as possible gives 1 → 2 → 3 → 6 for 12, which is the cheapest.
Example
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
Explanation
The path 1 → 3 → 1 → 1 → 1 sums to 7. Every other route runs through the 5 or the 4, both of which cost more than the detour saves.
Constraints
m == grid.length,n == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200