leetCode-70. 爬樓梯

題目：

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

輸入： 2

輸出： 2

解釋： 有兩種方法可以爬到樓頂。

1.  1 階 + 1 階

2.  2 階

示例 2：

輸入： 3

輸出： 3

解釋： 有三種方法可以爬到樓頂。

1.  1 階 + 1 階 + 1 階

2.  1 階 + 2 階

3.  2 階 + 1 階

解題思路：

動态規劃法。這個問題可以被分解為一些包含最優子結構的子問題，即它的最優解可以從其子問題的最優解來有效地建構，可以使用動态規劃來解決這一問題。

第i階可以由以下兩種方法得到：

在第 (i−1) 階後向上爬一階。

在第 (i−2) 階後向上爬 2 階。

是以到達第i階的方法總數就是到第(i−1) 階和第(i−2) 階的方法數之和。

代碼實作：

class Solution {
    public int climbStairs(int n) {
        
        int result = 0;
        int f0 = 1,f1 = 1,f2 = 2;
        if(n == 0 || n == 1)
            return f1;
        if(n == 2)
            return f2;
        for(int i=3;i<=n;i++){
            f0 = f1;
            f1 = f2;
            f2 = f0 + f1;
        }
       return f2; 
    }
}
           

效率：