grid has m rows and n columns, and every cell holds a cost of 0 or more. Walk from the top-left cell to the bottom-right cell, moving one cell right or one cell down at a time. The cost of a walk is the total of every cell it visits, counting both the first and the last.
Return the smallest cost any such walk can have.
Go right twice, down, right, then down: 3 + 1 + 1 + 1 + 2 + 1 = 9. It steps around both the 9 in the top-right corner and the 8 in the middle.
The cheapest first step is the 0 to the right, but every walk from there has to cross the 7 or the 8. Going down first instead costs 2 + 1 + 0 + 0 + 3 = 6.
With a single row there is only one walk, so the answer is the sum of the row.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200The cheapest walk to a cell comes in through either the cell above or the cell to its left, whichever is cheaper to reach. Always stepping to the cheaper neighbour does not work: a 0 can lead into a wall of large costs.
9