You are climbing a staircase with n steps.
Each time you can take either 1 step or 2 steps.
Your task is to return how many distinct ways you can reach the top.

---

Understanding the Problem

If n = 1
Ways = 1
(Only one move of 1 step)

If n = 2
Ways = 2
(1+1)
(2)

If n = 3
Ways = 3
(1+1+1)
(1+2)
(2+1)

If n = 4
Ways = 5
Patterns follow the Fibonacci sequence.

---

Approach (Explained in Simple Language)

This is a classic Dynamic Programming problem.

Observation:

To reach step n:

You must have come from step n−1 (taking 1 step)
Or from step n−2 (taking 2 steps)

So:

ways[n] = ways[n−1] + ways[n−2]

This is identical to Fibonacci numbers.

1. Base cases

ways[1] = 1
ways[2] = 2

2. Recurrence

For i from 3 to n:
ways[i] = ways[i−1] + ways[i−2]

3. Return ways[n]

Time complexity: O(n)
Space complexity: O(n) or O(1) if optimized.

---

Java Code (DP Array Method)

public class ClimbingStairs {

    public int climbStairs(int n) {

        if (n <= 2) {
            return n;
        }

        int[] dp = new int[n + 1];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        ClimbingStairs solution = new ClimbingStairs();
        System.out.println(solution.climbStairs(5));
    }
}

---

Java Code (Optimized Space O(1))

public class ClimbingStairsOptimized {

    public int climbStairs(int n) {

        if (n <= 2) {
            return n;
        }

        int prev1 = 2;
        int prev2 = 1;

        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

---

Dry Run

Let n = 5

dp array approach:

dp[1] = 1
dp[2] = 2

i = 3
dp[3] = dp[2] + dp[1] = 2 + 1 = 3

i = 4
dp[4] = dp[3] + dp[2] = 3 + 2 = 5

i = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

Final answer = 8

There are 8 possible ways to climb 5 stairs.

---

Why This Approach Works

The key observation is that the number of ways to reach step n depends only on the previous two steps:

From step n−1, take 1 step
From step n−2, take 2 steps

This creates a Fibonacci-like recurrence.
Dynamic Programming efficiently computes results using this recurrence.