# 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來逼近答案，但是測資大的時候會跑太久。

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，就可以改善時間複雜度了

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:

### 執行結果