grid is an m × n grid of non-negative integers. Walk from the top-left cell to the bottom-right cell, moving only right or down each step. The cost of a walk is the sum of every cell it visits, including both ends.
Write min_path_sum(grid: list[list[int]]) -> int: the cost of the cheapest walk. Don't modify grid.
Examples:
grid = [[2, 9, 1],
[3, 1, 1],
[8, 2, 4]]
min_path_sum(grid) == 11: 2 → 3 → 1 → 1 → 4.
min_path_sum([[7]]) == 7min_path_sum([[1, 2, 3]]) == 6
Constraints: 1 <= m, n <= 200, values 0..100. The number of walks grows exponentially, so trying them all times out; aim for O(m·n).
Show hint
the cheapest cost of reaching a cell depends only on the cheapest costs of reaching the cell above it and the cell to its left.