The cheapest way to the corner
The same two neighbours decide a cell's cost — take whichever is cheaper, then add this cell. About 11 minutes.
Tolls on every block
Same robot, same right-or-down moves, but now every block charges a toll. Instead of counting routes, you want the cheapest one.
That changes one word in the rule. You still arrive from above or from the left, but you'd only ever pick the cheaper of the two. So the cheapest cost to reach a block is its own toll plus the smaller of the two costs next to it. Counting added the two neighbours; choosing takes the smaller one.
The start costs its own number: 1.
The edges still have only one road
Along the top edge and down the left edge there's no choice to make: only one road leads there. So their costs are just running totals of the tolls so far.
Inside the grid, every box has two real options, and the smaller one wins. In the example the cheapest trip costs 7, going right along the top and then down the right side: 1, 3, 1, 1, 1.
up = best[r - 1][c] left = best[r][c - 1] best[r][c] = grid[r][c] + max(up, left)
Reaching the block above costs 9 at best, and reaching the block on the left costs 4. This block's toll is 2. What's the cheapest way to reach it?
- A6
- B11
- C15
Show the answer
6. Come in from the left (4), the cheaper side, and pay the toll of 2: 6.
Minimum path sum
You get a grid of non-negative integers. Starting at the top-left corner and moving only right or down, return the smallest possible sum of the numbers along a path to the bottom-right corner.
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] → 7
1 ≤ rows, cols ≤ 200 · 0 ≤ grid[i][j] ≤ 1,000