Min Cost Climbing Stairs
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
cost[i] is the price to step off stair i, and you then climb 1 or 2 stairs. You may start on stair 0 or 1. Find the cheapest way to reach the top (just beyond the last stair).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does it cost to stand on stair 0? On stair 1?
- Hint 2The top is index len(cost). How can you reach it?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
An escalator ticket system: each stair charges a toll when you leave it. Write on each stair the cheapest total toll to be standing there. Stairs 0 and 1 cost nothing to stand on (you can begin on either). For the next stair choose the cheaper of: the stair one below plus its toll, or the stair two below plus its toll. The top is one more stair beyond the last.
- The obvious way
Recursion over both options repeats subproblems: O(2^n).
- The key insight
reach[level] = cheapest total to be standing on that level. reach[0] = reach[1] = 0. For each level up to the top: reach[level] = min(reach[level - 1] + cost[level - 1], reach[level - 2] + cost[level - 2]). The answer is reach at the top.
- The algorithm
- reach[0] = reach[1] = 0.
- For each next level, take the cheaper of the two ways of arriving.
- Continue up to level len(cost), the top.
- Return reach[top].
Watch it run
Examplecost = [10, 15, 20]
Stairs 0 and 1 cost nothing to stand on (we may begin on either).
reach: 0, 0
Where people slip
- The top is one past the last index; the table has len(cost) + 1 slots.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def min_cost_climbing_stairs(cost):
top = len(cost)
reach = [0] * (top + 1) # cheapest total to be standing on each level
for level in range(2, top + 1):
from_one_below = reach[level - 1] + cost[level - 1]
from_two_below = reach[level - 2] + cost[level - 2]
reach[level] = min(from_one_below, from_two_below)
return reach[top]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.