Step i of a staircase has a toll cost[i], which you pay whenever you land on it. You may start on step 0 or step 1 (paying that step's toll). From any step you move up 1 or 2 steps. The top is just past the last step, at index len(cost), and reaching it is free.
Implement min_cost_climb(cost: list[int]) -> int: the smallest total toll to reach the top.
min_cost_climb([5, 2, 8]) # 2 start on step 1 (pay 2), jump 2 to the top
min_cost_climb([1, 50, 1, 1, 50, 1]) # 4 steps 0 -> 2 -> 3 -> 5 -> top
Constraints: 0 <= len(cost) <= 1000, 0 <= cost[i] <= 1000. With no steps at all, or a single step you can jump straight over, the answer is 0.
Show hint
let best[i] be the cheapest total for landing on step i; then best[i] = cost[i] + min(best[i-1], best[i-2]), and the answer is the cheaper of the last two steps (keep only two running values, not the whole table).