---
# System prepended metadata

title: 'Leetcode [No.70] Climbing Stairs (Easy)'
tags: [leetcode]

---

# Leetcode [No.70] Climbing Stairs (Easy)

## 題目
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?


## 思路
+ 這個解法是單純用費式數列+recursive來逼近答案，但是測資大的時候會跑太久。
```c++
class Solution {
public:
    int climbStairs(int n) {
        return fib(n); 
    }
    int fib(int n)
    {
        if(n <= 2) return n;
        else {return fib(n-1) + fib(n-2);}
    }
    
    
};
```

### 解法分析
+ time complexity: 很大


### 執行結果

TLE

## Dynamic Programming aprroach (top-down)


## 思路

因為上面的寫法會造成TLE，因此我把Recursive改寫成top-down的dp，就可以改善時間複雜度了

```C++=
class Solution {
public:
    
    int dp[46]={};

    int climbStairs(int n) {
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        
        return fib(n); 
        
    }
    int fib(int n)
    {
        if(dp[n] != 0) return dp[n];
        else 
        {
            dp[n] =  fib(n-1) + fib(n-2);
            return dp[n];
        }
    }
};
```

### 解法分析
+ time complexity: 

### 執行結果
![](https://hackmd.io/_uploads/BJBo_mlW6.png)
