Foundation drill for this topic
Easy Tabulation
In plain English: Count the number of different ways to reach the top of a staircase if you can take 1 or 2 steps at a time.
To reach step n you came from step n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2) — the same recurrence as Fibonacci.
Prompt
You can climb 1 or 2 steps at a time. How many distinct ways can you climb n stairs?
Try to write it from scratch before scrolling down.
Solution
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b # ways[i] = ways[i-1] + ways[i-2]
return b
# Test: climb_stairs(2) == 2
# Test: climb_stairs(3) == 3
# Test: climb_stairs(5) == 8Quick recall drills to reinforce this pattern.
dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Optimized to two variables. Final answer is min of last two.
def minCostClimbingStairs(cost):
a, b = cost[0], cost[1]
for i in range(2, len(cost)):
a, b = b, cost[i] + min(a, b)
return min(a, b)