假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1 階 + 1 階，2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1 階 + 1 階 + 1 階，1 階 + 2 階，2 階 + 1 階

首先分析題目推測數(shù)值
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 5
f(5) = 8
推斷結(jié)果值為一個不標準的斐波那契數(shù)列
進一步分析因為一次只能爬1或者2個臺階
當 n>=3的時候,
我們分析：第一步可以走1步，或者走2步 走一步之后我們還剩 n-1步的臺階需要走，走2步還剩n-2步臺階
因此可以定義狀態(tài)方程

n=1時 f(1) = 1
n=2時 f(2) = 2
n>=3時 f(n) = f(n-2)+f(n-1)

我們可以很容易想到一個標準的遞歸

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

遞歸求解相當于構(gòu)建一個二叉樹，然后遍歷所有節(jié)點，因此
時間復雜度O(2^n)，空間復雜度相當于二叉樹的高度n O(n)
由于時間復雜度太高，當n值很大的時候計算次數(shù)會爆炸??！
分析問題之后修改代碼邏輯如下

public int climbStairs(int n) {
       int[]nums = new int[n];
        int result = 0;
        for(int i=1;i<=n;i++){
            if(i==1){
                result = 1;
            }
            if(i == 2){
                result = 2;
            }
            if(i>=3){
                result = nums[i-2]+nums[i-3];
            }
            nums[i-1] = result;
        }
        return result;
    }

將每一次循環(huán)中生成的f(n)保存到數(shù)組中，后續(xù)計算f(n+1)直接從數(shù)組中獲取之前保存的數(shù)值相加
如此將時間復雜度變?yōu)镺(n),空間復雜度為數(shù)組的長度O(n);
然后查詢網(wǎng)上其他算法，發(fā)現(xiàn)可以使用尾遞歸來進一步壓縮空間復雜度為O(1)

 public int climbStairs(int n) {
        return fib(1,2,n);
    }

    public int fib(int first,int second,int n){
        if(n==1){
            return first;
        }
        if(n==2){
            return second;
        }
        if(n==3){
            return first+second;
        }
        return fib(second,first+second,n-1);
    }