A staircase has len(toll) steps, numbered from 0 at the bottom. Landing on step i costs toll[i]. You start on the ground just below step 0 and want to reach the landing just above the last step. Each move goes up 1, 2 or 3 positions, so from the ground you can land on step 0, 1 or 2, and you can reach the landing from any of the last three steps. The ground and the landing are free.
Write min_toll_climb(toll: list[int]) -> int that returns the smallest total toll for the climb.
min_toll_climb([4, 9, 2, 8, 7, 1]) # 3 ground -> step 2 -> step 5 -> landing
min_toll_climb([5, 5, 5, 5]) # 5 ground -> step 1 -> landing
min_toll_climb([7, 3]) # 0 stride straight over both steps
min_toll_climb([]) # 0
Constraints: 0 <= len(toll) <= 10^5, 0 <= toll[i] <= 10^4.
Trying every route is exponential, and a recursive search that walks the staircase one step per call runs out of stack on 100,000 steps. Aim for O(n) time and O(1) extra space.
Show hint
The cheapest way to land on step i depends only on the cheapest ways to land on the three steps just below it.