DSA With AI
Week 7 ยท 1-D Dynamic Programming

Climbing Stairs

Count how many distinct sequences of 1-step and 2-step moves reach exactly stair n.

Easy 1-D Dynamic Programming Week 7 Practice runner

Frame the problem

  • The order of moves matters: 1+2 and 2+1 are different.
  • Each state depends only on the previous two states.
  • The answer grows like Fibonacci numbers.
1. Reveal example inputs and outputs

Example 1

Input:

climb_stairs(3)

Output:

3

Example 2

Input:

climb_stairs(1)

Output:

1
2. Brute force first

Draw the recursion tree for n = 5. Which subproblems appear more than once?

3. Reveal the insight ladder
  1. The last move into stair n is either from n - 1 or from n - 2.
  2. Therefore ways(n) = ways(n - 1) + ways(n - 2).
  3. Memoization removes repeated recursion work.
  4. A bottom-up version only needs the previous two counts.
4. Dry run before code
  1. ways(1) = 1, ways(2) = 2.
  2. ways(3) = ways(2) + ways(1) = 3.
  3. ways(4) = ways(3) + ways(2) = 5.
  4. ways(5) = ways(4) + ways(3) = 8.
5. Reveal final Python solution 
def climb_stairs(n):
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Complexity: Time O(n), space O(1).

Interview narration

  • I will define the state as the number of ways to stand exactly on stair i.
  • The transition comes from the final move, which makes the recurrence exhaustive and non-overlapping.
  • Because each state only needs the previous two, I can compress the DP table into two variables.

Common traps

  • Returning Fibonacci(n) with the wrong base alignment.
  • Treating 1+2 and 2+1 as the same combination.
  • Using recursion without memoization and producing exponential runtime.

Follow-up drills

1. Allow steps of size 1, 2, or 3 and derive the recurrence.

The final move into stair n can come from n - 1, n - 2, or n - 3, so ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3). Base cases should handle n = 0 as one completed path if you write the general DP loop.

2. Allow an arbitrary set of step sizes and write the DP transition.

Let steps be the allowed positive step sizes. Define dp[0] = 1. For each stair i from 1 to n, dp[i] = sum(dp[i - step] for step in steps if i - step >= 0). This costs O(n * len(steps)) time and O(n) space unless the max step is small enough for a rolling window.

3. What changes if some stairs are blocked?

Keep the same state, but set dp[i] = 0 for blocked stairs. For unblocked stairs, compute the normal transition from reachable previous stairs. This checks whether you understand DP as reachability/counting over valid states, not just Fibonacci memorization.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.