Climbing Stairs DP DSA Solution

Learning Outcome

After this lesson, you should be able to turn repeated recursive choices into a simple recurrence with constant memory.

Problem Statement

Given n stairs, return how many distinct ways you can climb to the top when each move can take 1 or 2 steps.

Input	Output	Why
`n = 4`	`5`	The valid ways are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.

Brute Force Approach

Try every sequence of 1-step and 2-step moves recursively. This repeats the same subproblems many times.

Optimized Approach

Let ways[n] = ways[n

1] + ways[n
2]. Keep only the previous two values because each state depends on two earlier states.

Exact Pseudocode

if n <= 2:
  return n
one = 1
two = 2
for step from 3 to n:
  current = one + two
  one = two
  two = current
return two

Reference Code

class Solution:
    def climbStairs(self, n):
        if n <= 2:
            return n

        one, two = 1, 2
        for step in range(3, n + 1):
            current = one + two
            one = two
            two = current
        return two

Sample Dry Run

Step	State	Result
Base	ways(1)=1, ways(2)=2	one=1, two=2
Step 3	current = 1 + 2	ways(3)=3
Step 4	current = 2 + 3	ways(4)=5
Return	two = 5	answer = 5

Complexity

Measure	Value	Reason
Time	O(n)	The loop computes each stair count once.
Space	O(1)	Only two rolling values are stored.

Edge Cases

n = 1 and n = 2 are base cases.
Starting the loop at the wrong step shifts the answer.
For very large n, confirm whether modulo is required.

Interview Checklist

Define the recurrence before writing code.
Use base cases that match the prompt.
Update rolling variables in the correct order.

FAQs

Why is this Fibonacci DP?

Each stair can be reached from one step before or two steps before, so the recurrence matches Fibonacci-style growth.

Why not store the full DP array?

You can, but only the previous two states are needed for the next state.

What is the core pattern?

Rolling-state linear DP.

Climbing Stairs: Fibonacci DP Pattern