# Climbing Stairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/climbing-stairs)
Canonical: https://scaleengineer.com/dsa/problems/climbing-stairs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Barclays](https://scaleengineer.com/companies/barclays), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Bolt](https://scaleengineer.com/companies/bolt), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Turing](https://scaleengineer.com/companies/turing), [Citadel](https://scaleengineer.com/companies/citadel), [Disney](https://scaleengineer.com/companies/disney), [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## Problem
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?

**Example 1:**

**Input:** n = 2
**Output:** 2
**Explanation:** There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

**Example 2:**

**Input:** n = 3
**Output:** 3
**Explanation:** There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

**Constraints:**

* `1 <= n <= 45`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's recurrence relation, `ways(n) = ways(n-1) + ways(n-2)`, into a recursive function. It's the most straightforward way to think about the problem but is highly inefficient.
**Time:** O(2^n) · **Space:** O(n)
**Pros:** Simple to write and understand as it directly models the problem's definition.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' error for moderately large values of `n` (e.g., n > 35).
### Explanation
The core idea is that to reach the `n`-th step, you must have come from either the `(n-1)`-th step (by taking one step) or the `(n-2)`-th step (by taking two steps). The total number of ways is the sum of the ways to reach these two preceding steps. We define a function `climbStairs(n)` that calls itself for `n-1` and `n-2` and sums their results. The base cases are for `n=1` (1 way) and `n=2` (2 ways). This creates a large recursion tree where the number of ways for the same step is calculated multiple times, leading to an exponential time complexity.

```java
public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}
```
### Algorithm
- Define a function `climbStairs(n)`.
- Handle the base cases: if `n` is 1, return 1; if `n` is 2, return 2.
- For other values of `n`, make a recursive call: `return climbStairs(n - 1) + climbStairs(n - 2);`.

## Recursion with Memoization
This approach, also known as top-down dynamic programming, improves upon the brute-force recursion by storing the results of subproblems in a cache (the memoization table). This avoids redundant calculations for the same step, significantly improving performance.
**Time:** O(n) · **Space:** O(n)
**Pros:** Drastically more efficient than brute-force, with linear time complexity.; Maintains the logical structure of the recursive solution.
**Cons:** Requires extra space for the memoization array.; Incurs the overhead of recursive function calls.
### Explanation
We observe that the brute-force approach recomputes the number of ways for the same step multiple times. To optimize this, we use an array, `memo`, to store the result for each step `i` once it's computed. Before computing `climbStairs(i)`, we first check if `memo[i]` has already been calculated. If it has, we return the stored value. If not, we compute it recursively, store the result in `memo[i]`, and then return it. This ensures that each subproblem is solved only once.

```java
public class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return climb(n, memo);
    }

    private int climb(int n, int[] memo) {
        if (n <= 2) {
            return n;
        }
        if (memo[n] > 0) {
            return memo[n];
        }
        memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
        return memo[n];
    }
}
```
### Algorithm
- Create a memoization array `memo` of size `n + 1` to store computed results.
- Define a helper function, say `climb(n, memo)`.
- In the helper function, handle base cases: if `n <= 2`, return `n`.
- Before computing, check if `memo[n]` has a stored result. If yes, return it.
- If not, compute the result recursively: `memo[n] = climb(n - 1, memo) + climb(n - 2, memo)`.
- Store the result in `memo[n]` and return it.

## Bottom-Up Dynamic Programming
This approach, also known as bottom-up dynamic programming, solves the problem iteratively. It builds the solution from the base cases up to the desired step `n`, avoiding recursion entirely.
**Time:** O(n) · **Space:** O(n)
**Pros:** Efficient with linear time complexity.; Avoids recursion overhead, which can be slightly faster than memoization in practice.
**Cons:** Uses O(n) space for the DP array, which is not optimal.
### Explanation
We can recognize that `climbStairs(n)` is the `n`-th number in a Fibonacci-like sequence. We can build this sequence from the bottom up. We create a DP array, `dp`, of size `n + 1`, where `dp[i]` will store the number of ways to reach the `i`-th step. We initialize the base cases `dp[1] = 1` and `dp[2] = 2`. Then, we iterate from `i = 3` to `n`, filling the `dp` array using the same recurrence relation: `dp[i] = dp[i-1] + dp[i-2]`. The final answer is the value stored in `dp[n]`.

```java
public class Solution {
    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];
    }
}
```
### Algorithm
- If `n <= 2`, return `n`.
- Create a DP array `dp` of size `n + 1`.
- Initialize the base cases: `dp[1] = 1`, `dp[2] = 2`.
- Loop from `i = 3` to `n`.
- In the loop, calculate `dp[i] = dp[i - 1] + dp[i - 2]`.
- After the loop, return `dp[n]`.

## Space-Optimized Dynamic Programming
This approach optimizes the bottom-up DP solution by reducing the space complexity from `O(n)` to `O(1)`. It's one of the most common and efficient solutions for this problem.
**Time:** O(n) · **Space:** O(1)
**Pros:** Highly efficient in both time and space.; Optimal for typical interview constraints.
**Cons:** The logic might be slightly less direct to understand compared to the DP array approach.
### Explanation
When calculating the number of ways for the current step `i`, we only need the results for the previous two steps, `i-1` and `i-2`. There is no need to store the entire DP array. We can use just two variables to keep track of the last two values. Let's use `one_step_back` to store the ways for step `i-1` and `two_steps_back` for step `i-2`. We iterate from 3 to `n`, and in each step, we calculate the `current` number of ways by summing `one_step_back` and `two_steps_back`. Then we update our pointers: `two_steps_back` becomes the old `one_step_back`, and `one_step_back` becomes the `current` value.

```java
public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int two_steps_back = 1;
        int one_step_back = 2;
        for (int i = 3; i <= n; i++) {
            int current_ways = one_step_back + two_steps_back;
            two_steps_back = one_step_back;
            one_step_back = current_ways;
        }
        return one_step_back;
    }
}
```
### Algorithm
- Handle base cases: if `n <= 2`, return `n`.
- Initialize two variables: `two_steps_back = 1` (for `n=1`) and `one_step_back = 2` (for `n=2`).
- Loop from `i = 3` to `n`.
- Inside the loop, calculate `current_ways = one_step_back + two_steps_back`.
- Update the variables: `two_steps_back = one_step_back` and `one_step_back = current_ways`.
- After the loop, return `one_step_back`.

## Binet's Formula
This is a mathematical approach that uses a closed-form formula to calculate the n-th Fibonacci number directly. It is the most time-efficient approach, with logarithmic time complexity.
**Time:** O(log n) · **Space:** O(1)
**Pros:** The most time-efficient approach.; Constant space complexity.
**Cons:** Relies on floating-point arithmetic, which can have precision issues for very large numbers (though not an issue for `n <= 45`).; Less intuitive and harder to derive during an interview if not already known.
### Explanation
The number of ways to climb `n` stairs corresponds to the `(n+1)`-th Fibonacci number (`F_{n+1}`), where the sequence starts `F_1=1, F_2=1, ...`. Binet's formula provides a direct way to calculate the `k`-th Fibonacci number: `F_k = (φ^k - ψ^k) / √5`, where `φ = (1 + √5) / 2` is the golden ratio. Since the second term in the numerator is very small, the formula can be simplified to finding the nearest integer to `φ^k / √5`. We need to calculate the result for `k = n + 1`. The `Math.pow(base, exp)` function typically has a time complexity of `O(log exp)`, making this approach extremely fast.

```java
public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double phi = (1 + sqrt5) / 2;
        double result = Math.pow(phi, n + 1) / sqrt5;
        return (int) Math.round(result);
    }
}
```
### Algorithm
- Calculate `sqrt5 = Math.sqrt(5)`.
- Calculate the golden ratio `phi = (1 + sqrt5) / 2`.
- Calculate `phi` raised to the power of `n + 1` using `Math.pow(phi, n + 1)`.
- Divide the result by `sqrt5`.
- Round the final result to the nearest integer and cast it to `int`.

# Solutions
### Java

```java
class Solution {
public
  int climbStairs(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
      int c = a + b;
      a = b;
      b = c;
    }
    return b;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var climbStairs = function (n) {
  let a = 0,
    b = 1;
  for (let i = 0; i < n; ++i) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
};

```

### CPP

```cpp
class Solution {
public:
  int climbStairs(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
      int c = a + b;
      a = b;
      b = c;
    }
    return b;
  }
};

```

### Python

```python
class Solution:
    def climbStairs(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return b

```