###### tags: `LeetCode`,`Java`,`Easy`
# Easy－70. Climbing Stairs
### **題目連結：** [**Climbing Stairs**](https://leetcode.com/problems/climbing-stairs/description/)

### **解題方向**
* 這是一道比較經典的動態規劃問題。我們可以用 dp[i] 表示爬 i 階樓梯的方法數。那麼有 dp[i]=dp[i-1]+dp[i-2]，即爬到第 i 階樓梯的方法數等於爬到第 i-1 階樓梯的方法數加上爬到第 i-2 階樓梯的方法數。
* 為什麼是 dp[i-1]+dp[i-2] 呢？因為在爬到第 i 階樓梯的時候，我們有兩種方法：從第 i-1 階樓梯跨一步到第 i 階樓梯，或者從第 i-2 階樓梯跨兩步到第 i 階樓梯。而爬到第 i-1 階樓梯的方法數和爬到第 i-2 階樓梯的方法數，已經在前面求解過了。
* 但是，有一些有趣的數學特徵可以幫助我們更快地解決這個問題。我們注意到，如果我們不考慮“一步只能爬 1 或 2 級台階”的限制，那麼爬 n 級台階的方法數就是斐波那契數列的第 n+1 項，即 fib(n+1)。
* 斐波那契數列是一個非常經典的數學問題，定義為：第 0 項為 0，第 1 項為 1，從第 2 項開始，每一項等於前兩項的和。因此，斐波那契數列的前幾項是 0、1、1、2、3、5、8、13、21、34、……

### **完整程式碼**

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