Expert · Dynamic programming · 219 of 264
Cheapest path down
Walk from the top-left to the bottom-right of a grid of costs, moving only right or down. Find the smallest total cost (both corners count).
Input: r and c (up to 40), then r lines of c whole numbers. Output: the smallest total.
Examples
Input
3 3 1 3 1 1 5 1 4 2 1
Output
7
Input
1 3 1 2 3
Output
6
Input
2 2 9 1 1 9
Output
19
One more test checks other inputs when you press Check.
Stuck? The idea behind dynamic programming
Break the problem into smaller ones that repeat, and keep each answer in a table so it is worked out only once.
Decide what one cell of the table means ("the best total using the first i items"), how it follows from earlier cells, and where it starts.
n = 10
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
ways[i] = ways[i - 1] + (ways[i - 2] if i >= 2 else 0)
print(ways[n]) # climbing 10 stairs, 1 or 2 at a timeWatch for: Fill the table in an order where every cell it needs is already filled.