# 70.Climbing Stairs

## 1.Description(Easy)

You are climbing a stair case. It takes **n** steps to reach to the top.

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

**Example**

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3.

## 2.Code

(高频)统计方案个数+一维坐标

state: f(n) 表示爬了n 步后有几种爬法。-->开int\[n+1] 返回f(n)

function:f(n)=f(n-1)+f(n-2);

Initialize: f(0)=1, f(1)=1;

Answer: f(n)

```
 public int climbStairs(int n) {

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

        //state:number from 0 to n
        int[] path=new int[n+1];

        //Initialization:
        path[0]=1;
        path[1]=1;

        //function:
        for(int i=2;i<=n;i++){
            path[i]=path[i-1]+path[i-2];
        }

        //answer:
        return path[n];
    }
```

## Approach 1: Recursion <a href="#approach-1-recursion-tle" id="approach-1-recursion-tle"></a>

**Explanation**: The recursive solution uses the concept of Fibonacci numbers to solve the problem. It calculates the number of ways to climb the stairs by recursively calling the `climbStairs` function for (n-1) and (n-2) steps. However, this solution has exponential time complexity (O(2^n)) due to redundant calculations.

```java
class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}
```

## Approach 2: Memoization <a href="#approach-2-memoization" id="approach-2-memoization"></a>

**Explanation**: The memoization solution improves the recursive solution by introducing memoization, which avoids redundant calculations. We use an unordered map (`memo`) to store the already computed results for each step `n`. Before making a recursive call, we check if the result for the given `n` exists in the memo. If it does, we return the stored value; otherwise, we compute the result recursively and store it in the memo for future reference

```java
class Solution {
    public int climbStairs(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return climbStairs(n, memo);
    }
    
    private int climbStairs(int n, Map<Integer, Integer> memo) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (!memo.containsKey(n)) {
            memo.put(n, climbStairs(n-1, memo) + climbStairs(n-2, memo));
        }
        return memo.get(n);
    }
}
```

## Approach 3: Tabulation <a href="#approach-3-tabulation" id="approach-3-tabulation"></a>

**Explanation**: The tabulation solution eliminates recursion and uses a bottom-up approach to solve the problem iteratively. It creates a DP table (`dp`) of size n+1 to store the number of ways to reach each step. The base cases (0 and 1 steps) are initialized to 1 since there is only one way to reach them. Then, it iterates from 2 to n, filling in the DP table by summing up the values for the previous two steps. Finally, it returns the value in the last cell of the DP table, which represents the total number of ways to reach the top.

```java
class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        int[] dp = new int[n+1];
        dp[0] = dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
```

## Approach 4: Space Optimization <a href="#approach-4-space-optimization" id="approach-4-space-optimization"></a>

**Explanation**: The space-optimized solution further reduces the space complexity by using only two variables (`prev` and `curr`) instead of an entire DP table. It initializes `prev` and `curr` to 1 since there is only one way to reach the base cases (0 and 1 steps). Then, in each iteration, it updates `prev` and `curr` by shifting their values. `curr` becomes the sum of the previous two values, and `prev` stores the previous value of `curr`.

```java
class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int prev = 1, curr = 1;
        for (int i = 2; i <= n; i++) {
            int temp = curr;
            curr = prev + curr;
            prev = temp;
        }
        return curr;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/111climbing-stairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.