You don't stop lifting weights just because you own a car jack.
Leg day. The hardest topic for most people because the skill isn't the code, it's spotting the recurrence: how does the answer to a problem of size n relate to the answers to smaller subproblems? Once you have that, caching it is easy.
You can climb 1 or 2 steps at a time. Given n steps, how many distinct ways are there to reach the top?
def climb_stairs(n):
one, two = 1, 1
for _ in range(n - 1):
one, two = one + two, one
return one
The number of ways to reach step n is the ways to reach step n-1 plus the ways to reach step n-2 -- the Fibonacci recurrence in disguise. Only the last two values are ever needed, so there's no need for a full array.
Each step has a cost. Starting at step 0 or 1, moving 1 or 2 steps at a time, find the minimum cost to reach just past the last step.
def min_cost_climbing_stairs(cost):
prev, curr = 0, 0
for c in cost:
prev, curr = curr, min(prev, curr) + c
return min(prev, curr)
Same shape as Climbing Stairs, but now each step carries a cost instead of just counting paths: the cheapest way to reach step i is c[i] plus the cheaper of the two previous steps' running totals.
Same topic, no training wheels. Solve these on your own before you check the editorial.