Tutarlar ve ızgaralar

Tablo her zaman liste indeksiyle dolmaz. Bozuk para probleminde kutular tutarlardır: best[x], x tutarını yapan en az para sayısı. x için her parayı son para olarak denersin; geriye x - coin kalır ve onun cevabı tabloda hazırdır.

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

Izgarada kutu bir hücredir. Yalnızca sağa ve aşağı gidilebiliyorsa bir hücreye üstünden ya da solundan gelirsin: paths[r][c] = paths[r - 1][c] + paths[r][c - 1]. Duvar olan hücrenin değeri 0'dır; ilk satır ve ilk sütun, tek komşuları olduğu için ayrıca düşünülür.