Amounts and grids

A table is not always indexed by list position. In the coin problem the boxes are amounts: best[x] is the fewest coins that make x. For x you try each coin as the last one; that leaves x - coin, whose answer is already in the table.

1INF = float("inf")
2best = [0] + [INF] * amount
3for x in range(1, amount + 1):
4    for coin in coins:
5        if coin <= x:
6            best[x] = min(best[x], best[x - coin] + 1)
7return best[amount] if best[amount] != INF else -1

Infinity stands for "cannot be made yet": min drops it by itself, and if it is still infinity at the end the amount cannot be made at all. best[0] = 0: the amount zero takes zero coins.

On a grid a box is a cell. If you may only move right and down, you reach a cell from above or from the left: paths[r][c] = paths[r - 1][c] + paths[r][c - 1]. A wall cell holds 0; the first row and the first column have one neighbour each and need their own thought.

Tasks