AI Hints
Home›DSA in Python Tutorial›Dynamic Programming
DSA in Python · Lesson 91 of 132

Practice: Climbing Stairs

Counting the ways.

⏱ 2 min read▶ Video at 1:48:40🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

You're climbing a staircase with N steps. Each time, you can climb one step, or two. How many different ways are there to reach the top? Pause. Think about the very last move.

Practice: Climbing Stairs
From the video: Practice: Climbing Stairs
  • N steps
  • Climb 1 or 2 at a time
  • How many ways?

Thinking about the last move

To reach step N, your last move came from step N minus one, or step N minus two. So the ways to reach N are the ways to reach N minus one, plus the ways to reach N minus two. That's the same pattern as Fibonacci. We fill a table from the bottom. Run it. Ten steps can be climbed in eighty nine different ways.

stairs.pypython
def climb(n):
    ways = [1, 1]
    for i in range(2, n + 1):
        ways.append(ways[i - 1] + ways[i - 2])
    return ways[n]

for n in [1, 2, 3, 4, 10]:
    print(n, "steps:", climb(n), "ways")
Output
1 steps: 1 ways
2 steps: 2 ways
3 steps: 3 ways
4 steps: 5 ways
10 steps: 89 ways

The DP recipe

Every dynamic programming problem follows the same recipe. Define what one entry in the table means. Here, the ways to reach step I. Find how it's built from smaller entries. Set the starting values. Then fill the table in order, and read off the answer.

keyvalue
1. Defineways[i] = ways to reach step i
2. Relateways[i-1] + ways[i-2]
3. Startways[0] = ways[1] = 1
4. Fillin order, read the answer

Summary

The ways to climb N stairs equal the ways to N minus one, plus N minus two. Define, relate, start, and fill. Next, fixing the coin problem that greedy got wrong.

Key takeaways
  • Think about the last move
  • Build from smaller answers
  • Fill a table
Next up: Practice: Coin Change — fewest coins, done right