Difficulty: Easy1-D Dynamic Programming

Climbing Stairs

Problem in Plain English

Count how many distinct ways there are to reach step n when every move climbs either 1 or 2 steps.

Problem Statement

You are climbing a staircase with n steps. Each move climbs either 1 step or 2 steps.

Return the number of distinct move sequences that land exactly on step n.

Constraints

1 <= n <= 45
The answer fits in a 32-bit signed integer.

Examples

Example 1

Input: n = 5
Output: 8

The routes are [1, 1, 1, 1, 1], [2, 1, 1, 1], [1, 2, 1, 1], [1, 1, 2, 1], [1, 1, 1, 2], [2, 2, 1], [2, 1, 2], and [1, 2, 2]. Order matters: placing a two-step move at different positions creates different routes.

Example 2

Input: n = 3
Output: 3

The three routes are [1, 1, 1], [1, 2], and [2, 1]. The last two contain the same moves in different orders and must both be counted.

Example 3

Input: n = 1
Output: 1

Only [1] reaches the first step. A two-step move overshoots, so the smallest valid input has exactly one route.

Example 4

Input: n = 2
Output: 2

The two routes are [1, 1] and [2]. This second seed is needed before the recurrence can combine two smaller positive staircases.

Intuition

Group routes by their final move. A route to step 5 ends with one step from step 4 or two steps from step 3. There are 5 routes to step 4 and 3 to step 3, so step 5 has 8 routes. These groups cannot overlap because their final moves differ. Repeating this reasoning gives a recurrence; remembering the last two counts avoids counting the same smaller staircase again and again.

Approaches

Recursion Without Memo

Solution Details

Reveal Recursion Without Memo: intuition, complexity, and code

Intuition

Recursively count the routes ending with a one-step move and those ending with a two-step move. For n = 5, this asks for counts at 4 and 3, which themselves ask for smaller counts. The same request for 3 appears twice; without memoization neither result is remembered, so repeated subproblems make larger inputs impractical.

Step-by-Step Logic

Return 1 for n = 1 and 2 for n = 2; these are the stopping cases. For Example 1, n = 5 needs recursive work.
For any larger staircase, first evaluate climbStairs(n - 1), then climbStairs(n - 2), and add the counts. The call for 5 first enters 4, which first enters 3.
The call for 3 combines the base returns 2 and 1 into 3. The call for 4 combines that 3 with a new base call for 2, returning 5.
Evaluate the second branch of 5 by calling 3 again. It repeats the two base calls and returns 3; combine the saved left result 5 with 3 and return 8.

Why It Works

The base cases return the actual route counts for one step (1) and two steps (2). For any larger n, removing the final move maps each route uniquely to either a route for n - 1 or a route for n - 2. Conversely, appending the corresponding final move creates one valid route to n. The groups are disjoint and cover every route, so adding their counts is correct. Induction on n proves every returned count.

Dry Run

Recursion Without Memo: variable states at each step
Execution event	Call path (n values)	Saved left count / result
Enter root	5	wait for 4 then 3
Enter left branch	5 -> 4	wait for 3 then 2
Enter left branch	5 -> 4 -> 3	wait for 2 then 1
Enter and return base	5 -> 4 -> 3 -> 2	return 2; parent 3 saves 2
Enter and return base	5 -> 4 -> 3 -> 1	return 1
Combine and return	5 -> 4 -> 3	2 + 1 = 3; parent 4 saves 3
Enter and return base	5 -> 4 -> 2	return 2
Combine and return	5 -> 4	3 + 2 = 5; root 5 saves 5
Enter right branch	5 -> 3	recompute 3; wait for 2 then 1
Enter and return base	5 -> 3 -> 2	return 2; parent 3 saves 2
Enter and return base	5 -> 3 -> 1	return 1
Combine and return	5 -> 3	2 + 1 = 3
Combine and return root	5	5 + 3 = 8; return 8

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the number of steps. Non-base calls branch twice and the depth is O(n), giving the loose upper bound O(2^n); branches have different lengths, so the tree does not double at every level. More tightly, the call count grows as Theta(phi^n), where phi is the golden ratio. O(n) stack frames hold arguments and pending sums, with no memo table. The largest valid input, n = 45, is correct mathematically but takes billions of calls and is impractical for this teaching baseline; use the rolling approach for the full bound. Counts and intermediate sums fit signed 32-bit integers throughout the stated range.

Code

Solution.java

1class Solution {2    public int climbStairs(int n) {3        if (n <= 1) return 1;4        if (n == 2) return 2;5        // Partition routes by the final move; repeated subproblems are not cached.6        return climbStairs(n - 1) + climbStairs(n - 2);7    }8}

Hints

Hint 1

Ask where the final move comes from: step n is reached from step n - 1 with a single or from step n - 2 with a double.

Hint 2

The final-move groups give

W(n) = W(n - 1) + W(n - 2)

with seeds

W(1) = 1

and

W(2) = 2

Hint 3

Only the last two counts matter, so keep two variables and roll them forward instead of building a table.

Edge Cases

n = 1 returns 1 from the seed with no loop or recursive branching.
n = 2 has two routes and returns directly in both snippets; n = 3 is the first input that combines two earlier counts.
n = 45 returns 1836311903. This fits a signed 32-bit integer, but reaching it with uncached recursion is impractical.
The statement excludes n = 0. In a recurrence using zero as a seed, the empty route counts once; that convention is not an additional valid input here.

Common Mistakes and Interview Tips

Using Fibonacci seeds 0 and 1 directly gives the wrong offset: staircase counts begin 1, 2, 3, 5, 8 for positive n.
Overwriting prev2 before calculating current loses one old count. Sum first, then shift both variables.
Stopping the loop before i = n returns the count for the previous step.
Treating [1, 2] and [2, 1] as the same route undercounts: move order matters.
Allocating a full n-sized table when the recurrence only reads the previous two entries wastes linear space.
Recomputing shared steps with plain recursion explodes to exponential time on larger n.

Key Takeaway

When each state depends only on a fixed window of previous states, a recurrence plus a few rolling variables turns exponential recursion into linear time and constant space.