🧩 Puzzle · Apply Climbing Stairs
Fill the steps
How many ways to climb to stair n, taking 1 or 2 steps at a time? To land on stair n you either stepped up from n-1 or jumped from n-2 — so ways(n) = ways(n-1) + ways(n-2). The two base cases are given. Fill the table from the bottom up, each cell summing the two below it.
ways(n) = ways(n-1) + ways(n-2) · fill from the bottom up
ways(0)1
ways(1)1
ways(2)?
ways(3)
ways(4)
ways(5)
ways(6)
Base cases are filled: ways(0)=1, ways(1)=1. Fill each higher stair = sum of the two below it.
ways(2) =
Purple = given base cases. Green = your filled cells. Each one reuses the two below.no misses