Leetcode 70: Climbing Stairs

1. Problem Statement (Simple Explanation)

You need to climb a staircase with n steps.

• Each move you can climb either 1 step or 2 steps.

• You want to know: in how many distinct ways can you reach exactly step n from step 0?

2. Examples

Example 1:

Input: n = 2

Ways:

1. 1 + 1

2. 2

Total: 2

Output: 2

Example 2:

Input: n = 3

Ways:

1. 1 + 1 + 1

2. 1 + 2

3. 2 + 1

Total: 3

Output: 3

3. Approach – Fibonacci-style DP (O(n), O(1) space)

Let f(n) = number of ways to climb n steps.

To reach step n, your last move could be:

• From step n-1 with a 1-step jump → f(n-1) ways.

• From step n-2 with a 2-step jump → f(n-2) ways.

So: f(n) = f(n-1) + f(n-2)

Base cases:

• f(1) = 1 (only 1)

• f(2) = 2 (1+1, 2)

This is exactly the Fibonacci recurrence starting from those seeds.

We can compute iteratively in O(n) time and O(1) space.

Pseudo-code:

Complexity:

• Time: O(n)

• Space: O(1)

Given n <= 45, numbers stay within 32-bit int.

4. Java code

5. C code

Note: The C version modifies path in-place due to strtok, so in strict environments you should first strdup() the input string.

6. C++ code

7. Python code

8. JavaScript code