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

Recall & Review

beginner

What is the Climbing Stairs Problem?

It is a problem where you count how many distinct ways you can climb to the top of a staircase with n steps, taking either 1 or 2 steps at a time.

beginner

What is the base case for the Climbing Stairs Problem?

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

intermediate

What is the relation between the number of ways to climb n steps and smaller steps?

The number of ways to climb n steps equals the ways to climb (n-1) steps plus the ways to climb (n-2) steps.

intermediate

How can you optimize the Climbing Stairs solution to use less memory?

Instead of storing all previous results, keep only the last two counts since each new count depends only on the previous two.

beginner

Write the TypeScript function signature for the Climbing Stairs Problem.

function climbStairs(n: number): number

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

A 4

B 2

C 3

D 5

The ways are: (1+1+1), (1+2), (2+1), so total 3 ways.

What is the time complexity of the dynamic programming solution for the Climbing Stairs Problem?

A O(n)

B O(n^2)

C O(2^n)

D O(log n)

The solution calculates each step once, so it runs in linear time O(n).

Which of these is the correct 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 reach step n is the sum of ways to reach steps n-1 and n-2.

What is the minimum number of steps you can take at once in the Climbing Stairs Problem?

A 2

B 0

C 3

D 1

You can take either 1 or 2 steps at a time, so minimum is 1.

If n = 1, how many ways are there to climb the stairs?

A 1

B 0

C 2

D 3

With 1 step, only one way: take one step.

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

Think about how the number of ways to climb depends on previous steps.

Describe how to optimize the space used in the Climbing Stairs Problem solution.

Focus on what data is needed to compute the next step.