64. Minimum Path Sum
You are given an m x n grid of non-negative integers as a 2D array. Starting on the top-left cell and moving only one cell right or one cell down per step, walk to the bottom-right cell.
Every route has a cost: the sum of the values of every cell it visits, including both the start and finish cells. Return the smallest cost achievable over all routes.
Your function receives the grid and returns that minimum sum as an integer.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The cheapest route runs across the top and down the right side: 1 + 3 + 1 + 1 + 1 = 7, dodging the 5 and the 4.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: Going right, right, then down costs 1 + 2 + 3 + 6 = 12, the best of the three possible routes.
Constraints:
- 1 ≤ m, n ≤ 200
- 0 ≤ grid[i][j] ≤ 200
Hints:
Greedily stepping onto the cheaper neighbor can trap you behind expensive cells later. Think instead about the cheapest way to *arrive* at each cell.
The cheapest cost to reach cell (i, j) is grid[i][j] plus the smaller of the cheapest costs to reach the cell above and the cell to the left. First-row and first-column cells have only one way in.
You only ever look one row up, so a single 1D array updated left to right carries all the state you need.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Expected output: 7