Algorithm Day82 - Climbing Stairs

Posted on In , Views:

🧩 Problem Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

💬 Examples

Example 1

1
2
3
Input: n = 2
Output: 2
Explanation: 1 step + 1 step OR 2 steps.

Example 2

1
2
3
Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1.

💡 Intuition

This is a dynamic programming problem, equivalent to computing the Fibonacci sequence.

  • Let dp[i] be the number of ways to climb i steps.
  • Transition: dp[i] = dp[i-1] + dp[i-2].
  • Base cases: dp[1] = 1, dp[2] = 2.

We can optimize space to O(1) by just keeping the last two states.

🔢 Java Code (DP Optimized)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

⏱ Complexity Analysis

  • Time: O(n) — linear iteration.
  • Space: O(1) — only two variables stored.

✍️ Summary

  • Equivalent to computing Fibonacci numbers.
  • Use DP or iterative approach for efficiency.
  • Space optimized to O(1).

Related problems

  • lc-746 — Min Cost Climbing Stairs
  • lc-509 — Fibonacci Number