LeetCode70. 爬樓梯——斐波那契額數列多種執行效率不同的解法

題目：

假設你正在爬樓梯。需要 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 階

如果這道題放在高中數學卷子中，最多是一道排在前面的選擇題，我會根據先挨着畫幾個“樓梯”，試一試并找出規律最多也就一兩分鐘的事情。現在不知道腦殼咋個了，遇到題沒有思路，不善于動手畫畫，多思考，最後還是查了點資料做出來的，發現這其實就是一個斐波那契數列（第三個數等于前兩個數之和），當然這樣的數列也是可以用遞歸來實作，不過執行效率沒有将值放在數組中高。

遞歸實作，代碼量最少，效率最低

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        else if(n==2){
            return 2;
        }
        else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }
}
           

數組實作，效率較高

class Solution {
    public int climbStairs(int n) {
        int temp[] = new int[n];
        if(n==1){
            return 1;
        }
        else if(n==2){
            return 2;
        }
        else{
            temp[0]=1;
            temp[1]=2;
            for(int k=2;k<n;k++){
                temp[k] = temp[k-1]+temp[k-2];//等于前兩個值之和
            }
        }
        return temp[n-1];
    }
}
           

也可以不用數組，這樣節省空間并且執行效率更高

class Solution {
    public int climbStairs(int n) {
        int last=0;//爬到目前樓梯的方法數
        if(n==1){
            return 1;//如果樓梯隻有一步，便隻有一種方法
        }
        else if(n==2){
            return 2;//如果樓梯有兩步，有兩種方法
        }
        else{//樓梯大于等于三步時
            int k=3;//k代表樓梯數
            int first = 1;//定義爬到目前樓梯前兩步的方法數，即斐波那契數列的第一個值
            int second = 2;//定義爬到目前樓梯前一步的方法數，即斐波那契數列的第二個值
            while(k<=n){//不能大于樓梯數
                last = first+second;//斐波那契數列目前值等于前兩個數之和
                first = second;//替換
                second = last;//替換
                k++;
            }
        }
        return last;
    }
}