爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意： 給定 n 是一個(gè)正整數(shù)。
示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1.1 階 + 1 階
2.2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.1 階 + 1 階 + 1 階
2.1 階 + 2 階
3.2 階 + 1 階

暴力法

分析

不妨舉個(gè)例子，假設(shè)需要5階才能到達(dá)樓頂，f(5)為到達(dá)樓頂?shù)姆椒〝?shù)。那么要到達(dá)第5階，只可能有2種情況：1.從第4階爬1個(gè)臺(tái)階；2.從第3階爬2個(gè)臺(tái)階；這就把問題轉(zhuǎn)化為求f(4)和f(3)，即f(5) = f(4) + f(3)，所以f(n) = f(n - 1) + f(n - 2)。

class Solution {
    public int climbStairs(int n) {
        
        //f(1) = 1, f(2) = 2;
        //f(n) = f(n - 1) + f(n - 2);
        if(n == 1) return 1;
        if(n == 2) return 2;

        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

總結(jié)

代碼雖然簡(jiǎn)單，但是我們畫出遞歸樹后會(huì)發(fā)現(xiàn)有很多冗余項(xiàng)，即很多重復(fù)計(jì)算，例如求f(11)，需要求 f(10) + f(9)，求f(10)又需要求f(9) + f(8)，求f(9)又需要求f(8) + f(7)，這里f(9)和f(8)分別計(jì)算了兩次，非常耗時(shí)，其時(shí)間復(fù)雜度為O(2^n)，提交也不通過。下面我將介紹兩種基于此算法的優(yōu)化算法。

記憶化遞歸

分析

上文我們分析到遞歸會(huì)有大量重復(fù)計(jì)算，事實(shí)上遞歸過程是有先后順序的，如果先前計(jì)算的結(jié)果可以存儲(chǔ)，那么后面需要用到的話就可以直接拿去用了，這樣時(shí)間復(fù)雜度降為O(n)，無疑是一次降維打擊。

class Solution {
    
    public int climbStairs(int n) {
        
        int[] meno = new int[n + 1]; //存儲(chǔ)每一次的結(jié)果，初始全為0
        return __climbStairs(n, meno);
    }
    
    public int __climbStairs(int n, int[] meno){
        
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(meno[n] > 0) return meno[n]; //大于0就證明已經(jīng)計(jì)算過了，直接返回
        meno[n] = __climbStairs(n - 1, meno) + __climbStairs(n - 2, meno);
        
        return meno[n];
    }
}

動(dòng)態(tài)規(guī)劃

分析

不難發(fā)現(xiàn)，這個(gè)問題可以被分解為一些包含最優(yōu)子結(jié)構(gòu)的子問題，即它的最優(yōu)解可以從其子問題的最優(yōu)解來有效地構(gòu)建，我們可以使用動(dòng)態(tài)規(guī)劃來解決這一問題。令 dp[i] 表示能到達(dá)第 i 階的方法總數(shù)，從上文的分析中易知該動(dòng)態(tài)轉(zhuǎn)移方程為dp[i] = dp[i - 1] + dp[ i - 2];

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

打表法

分析

如果單從通過這道題目來說，打表無疑是另辟蹊徑，既然網(wǎng)站有時(shí)間限制，而且測(cè)試用例很適合打表，那么我在本地把每一種階梯的方法數(shù)求出來，用一個(gè)容器存儲(chǔ)，傳入哪個(gè)階梯我就有哪個(gè)答案，時(shí)間復(fù)雜度為O(1)。

public class Solution {
    public int climbStairs(int n) {
        
        int result = 0;
        
        switch(n){
        case 1: result = 1; break;
        case 2: result = 2; break;
        case 3: result = 3; break;
        case 4: result = 5; break;
        case 5: result = 8; break;
        case 6: result = 13; break;
        case 7: result = 21; break;
        case 8: result = 34; break;
        case 9: result = 55; break;
        case 10: result = 89; break;
        case 11: result = 144; break;
        case 12: result = 233; break;
        case 13: result = 377; break;
        case 14: result = 610; break;
        case 15: result = 987; break;
        case 16: result = 1597; break;
        case 17: result = 2584; break;
        case 18: result = 4181; break;
        case 19: result = 6765; break;
        case 20: result = 10946; break;
        case 21: result = 17711; break;
        case 22: result = 28657; break;
        case 23: result = 46368; break;
        case 24: result = 75025; break;
        case 25: result = 121393; break;
        case 26: result = 196418; break;
        case 27: result = 317811; break;
        case 28: result = 514229; break;
        case 29: result = 832040; break;
        case 30: result = 1346269; break;
        case 31: result = 2178309; break;
        case 32: result = 3524578; break;
        case 33: result = 5702887; break;
        case 34: result = 9227465; break;
        case 35: result = 14930352; break;
        case 36: result = 24157817; break;
        case 37: result = 39088169; break;
        case 38: result = 63245986; break;
        case 39: result = 102334155; break;
        case 40: result = 165580141; break;
        case 41: result = 267914296; break;
        case 42: result = 433494437; break;
        case 43: result = 701408733; break;
        case 44: result = 1134903170; break;
        case 45: result = 1836311903; break;
        
        }
        return result;
    }
}

斐波那契公式

分析

從我們分析出來的遞歸公式可以看出這就是一個(gè)求斐波那契數(shù)的問題，那么根據(jù)斐波那契公式（公式通過求根公式或者數(shù)列的遞推式可以求出）我們可以直接求得結(jié)果。

public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}

參考文獻(xiàn)

參考文章：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/