All problems

Minimum Path Sum

Medium · dynamic programming

You are given a rectangular board of non-negative whole numbers. Each cell holds the cost of stepping on it.

A traveller starts in the top-left cell and wants to reach the bottom-right cell. On every move it goes one cell down or one cell right, never up or left, and it must stay on the board.

The cost of a route is the sum of the costs of every cell it visits, including the first and the last cell. Return the smallest cost of any route from the top-left cell to the bottom-right cell.

Examples

Example 1

Input: grid = [[2, 1, 4], [3, 8, 2], [5, 1, 1]]

Output: 10

Right, right, down, down costs 2 + 1 + 4 + 2 + 1 = 10. The other five routes cost between 12 and 16.

Example 2

Input: grid = [[4, 2], [1, 7]]

Output: 12

Going down first costs 4 + 1 + 7 = 12. Going right first costs 4 + 2 + 7 = 13.

Example 3

Input: grid = [[5, 0, 3, 2]]

Output: 10

A single row leaves only one route, so the answer is the sum of the row.

Constraints