This is a common Data Structures & Algorithms (Dynamic Programming) interview and practice question. Below is the full answer with a clear, step-by-step explanation.

Question

Problem You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top? Input n = 5 Expected Return 8

Answer & Explanation

What the problem is asking

You have a staircase with n steps. From any step you may move either one step forward or two steps forward. How many different sequences of moves will land you exactly on the top (step n)?

For the concrete input n = 5 the answer should be 8.

Why the answer is 8

Think about the last move you make to reach step n.

If the last move is a single step, then before that move you must have been on step n‑1.
If the last move is a double step, then before that move you must have been on step n‑2.

Therefore the total number of ways to reach step n is:

ways(n) = ways(n‑1) + ways(n‑2)

That recurrence is exactly the Fibonacci recurrence. The only thing that changes are the starting values (the “seed” cases).

Base cases

ways(1) = 1 – there is only one way to stand on the first step (a single 1‑step move).
ways(2) = 2 – either two 1‑step moves (1+1) or one 2‑step move (2).

With these two seeds the recurrence generates the whole sequence:

n : 1  2  3  4  5  6 …
ways: 1  2  3  5  8 13 …

So for n = 5 we get ways(5) = 8.

How to compute it efficiently

A naïve recursive implementation would call itself many times and run in exponential time. The recurrence is linear, so we can compute it iteratively in O(n) time while keeping only the last two values, giving O(1) extra space.

Algorithm (bottom‑up):

If n is 1 or 2, return n directly.
Initialise two variables:
- a = 1 (ways for step 1)
- b = 2 (ways for step 2)
Loop from step 3 up to step n:
- c = a + b (ways for the current step)
- Move the window forward: a = b, b = c.
After the loop, b holds ways(n). Return it.

Because each iteration does only a couple of integer additions, the runtime is linear in n and the memory usage stays constant.

Reference implementation (Python‑style)

def climb_stairs(n):
    # Base cases
    if n <= 2:
        return n

    # a = ways for step i‑2, b = ways for step i‑1
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b   # compute ways for step i and shift window
    return b

# Example
print(climb_stairs(5))   # → 8

The loop runs three times (for i = 3, 4, 5) and produces the sequence 1, 2, 3, 5, 8, so the function returns 8 for the given input.

Key take‑aways you should remember

The problem reduces to the Fibonacci recurrence because the last move can be 1 or 2 steps.
Correct base cases are ways(1)=1 and ways(2)=2.
An iterative bottom‑up solution with two variables gives O(n) time and O(1) space.
For n = 5 the computed value is 8.

Understanding this reasoning lets you solve any instance of the “climbing stairs” problem quickly and explain why your solution works.