Climbing Stairs Problem in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Climbing Stairs Problem?

It is a problem where you count how many ways you can climb to the top of a staircase if you can take either 1 or 2 steps at a time.

beginner

What is the base case for the Climbing Stairs Problem?

If there is 1 step, there is only 1 way to climb it. If there are 2 steps, there are 2 ways: (1+1) or (2).

intermediate

How do you calculate the number of ways to climb n stairs?

The number of ways to climb n stairs equals the sum of ways to climb (n-1) stairs and ways to climb (n-2) stairs.

intermediate

Why is the Climbing Stairs Problem similar to the Fibonacci sequence?

Because each number of ways depends on the sum of the two previous counts, just like Fibonacci numbers.

advanced

What is the time complexity of the simple recursive solution for the Climbing Stairs Problem?

It is exponential (O(2^n)) because it recalculates the same values many times.

How many ways are there to climb 3 stairs if you can take 1 or 2 steps at a time?

A 5

B 4

C 2

D 3

The ways are: (1+1+1), (1+2), (2+1) which totals 3.

What is the recurrence relation for the Climbing Stairs Problem?

A ways(n) = ways(n-1) - ways(n-2)

B ways(n) = ways(n-1) * ways(n-2)

C ways(n) = ways(n-1) + ways(n-2)

D ways(n) = ways(n-1) / ways(n-2)

The number of ways to climb n stairs is the sum of ways to climb n-1 and n-2 stairs.

What is the simplest base case for the Climbing Stairs Problem?

A ways(1) = 1

B ways(2) = 3

C ways(0) = 1

D ways(3) = 2

There is only 1 way to climb 1 stair: a single step.

Which approach improves the time complexity of the Climbing Stairs Problem from exponential to linear?

A Memoization

B Brute force recursion

C Random guessing

D Sorting

Memoization stores results of subproblems to avoid repeated calculations.

If you can climb 1, 2, or 3 steps at a time, how does the recurrence relation change?

A ways(n) = ways(n-1) * ways(n-2) * ways(n-3)

B ways(n) = ways(n-1) + ways(n-2) + ways(n-3)

C ways(n) = ways(n-1) - ways(n-2) - ways(n-3)

D ways(n) = ways(n-1) / ways(n-2) / ways(n-3)

You add the ways to climb n-1, n-2, and n-3 stairs because you can take 1, 2, or 3 steps.

Explain how to solve the Climbing Stairs Problem using dynamic programming.

Think about how you can use answers for smaller stairs to find answers for bigger stairs.

Describe why the Climbing Stairs Problem is related to the Fibonacci sequence.

Focus on how the count for step n depends on counts for steps n-1 and n-2.