70. Climbing Stairs

EasyOne-Dimensional Dynamic ProgrammingDynamic programming with two rolling variablesFibonacci-style linear DP

Climbing Stairs

You are climbing a staircase that takes n steps to reach the top. Each move you may climb either 1 or 2 steps. Return the number of distinct ordered ways to reach the top.

Open official problem prompt ↗

In plain English

Count how many different ordered sequences of 1-step and 2-step moves sum to exactly n.

Picture it like this

Hopping up stairs one or two at a time; the number of routes to a given step is just the sum of the routes to the two steps you could have jumped from.

Example

Input: n = 3
Output: 3
Why: The ways are 1+1+1, 1+2, and 2+1 -- three distinct orderings.

Constraints

1 <= n <= 45

Pattern lesson

See the pattern, then code

Fibonacci-style linear DP

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. To stand on step i you arrived either from step i-1 (a 1-step) or step i-2 (a 2-step), so ways(i) = ways(i-1) + ways(i-2).

New words, made simpleKnow these before the algorithm

Recurrence: A formula defining a value in terms of earlier values.
Base case: The smallest inputs answered directly, here 0 and 1 steps.
Rolling variables: Two running values that replace a full DP array.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Naive recursion

Recomputes the same subproblems exponentially.

Recurse ways(n)=ways(n-1)+ways(n-2) without memoization.

Time O(2^n)Space O(n)

Best choiceRolling two-variable DP

Linear time, constant space, no recursion overhead.

Iterate keeping only the last two counts.

Time O(n)Space O(1)

The rule we keep true

Invariant

After k iterations, a holds the number of ways to climb k steps and b holds the number of ways to climb k+1 steps.

Why this is correct

Reasoning

The final move onto step n is either a single step from n-1 or a double step from n-2, and those two arrival sets are disjoint and exhaustive; summing their counts counts every route exactly once, giving the Fibonacci recurrence.

The algorithm in three movesSay these aloud before coding

1Note that ways(0)=1 and ways(1)=1

ways(1)=1

2For each step add the counts of the two previous steps

ways(2)=2

3Roll the two variables forward n times

ways(3)=ways(2)+ways(1)=3

4Return the accumulated count

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reada=1, b=1

2 · AskBase cases for 0 and 1 steps.

3 · Update statea=1, b=1

4 · ResultOne way each to climb 0 or 1 step.

Key takeaway

Step counts build up Fibonacci-style until step 3 holds 3 ways.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Seed two counts
a and b both start at 1, representing ways to climb 0 and 1 steps respectively.
2
Lines 4-5Advance n times
Each iteration slides the window forward: the new b is a+b, and a takes the old b.
3
Lines 6Return
After n iterations a equals ways(n).

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 1 returns 1
n = 2 returns 2
Upper bound n = 45 fits comfortably in a Python int
No n = 0 case per constraints, but the code would return 1 correctly

Common beginner mistakes

Using plain recursion without memoization and timing out for larger n
Off-by-one errors in the number of loop iterations
Treating 1+2 and 2+1 as the same route -- order matters, so they are distinct

Check your understanding

Why is the answer the Fibonacci number rather than a combination count?

Climbing Stairs

Climbing Stairs

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming