這是悅樂書的第159次更新，第161篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級別的第18題（順位題號是70）。你正在爬樓梯，它需要n步才能達(dá)到頂峰。每次你可以爬1或2步，你可以通過多少不同的方式登頂？注意：給定n是一個(gè)正整數(shù)。例如：

輸入：2
輸出：2

說明：有兩種方法可以爬到頂端

1、1步 + 1步

2、2步

輸入：3
輸出：3

說明：有三種方法可以爬到頂端

1、1步 + 1步 + 1步

2、1步 + 2步

3、2步 + 1步

輸入：4
輸出：5

說明：有5種方法可以爬到頂端

1、1步 + 1步 + 1步 + 1步

2、1步 + 1步 + 2步

3、1步 + 2步 + 1步

4、2步 + 1步 + 1步

5、2步 + 2步

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測試。

02 第一種解法

關(guān)于題目，可以從簡單的條件開始推導(dǎo)。

當(dāng)n等于1的時(shí)候，有1種方式。

當(dāng)n等于2的時(shí)候，有2種方式。

當(dāng)n等于3的時(shí)候，有3種方式。

當(dāng)n等于4的時(shí)候，有5種方式。

當(dāng)n等于5的時(shí)候，有8種方式。

看到這，你會(huì)發(fā)現(xiàn)從n等于2開始，后一項(xiàng)等于前兩項(xiàng)的和，這時(shí)很容易想到遞歸，于是就有了第一種解法。

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

03 第二種解法

上面的解法，你應(yīng)該也發(fā)現(xiàn)問題了，運(yùn)行太慢了。有什么可以優(yōu)化的呢？既然只是求前兩個(gè)數(shù)的和，那么可以引用數(shù)組來存值，而不是每次都來重新算一次。

public int climbStairs2(int n) {
    int[] arr = new int[n+1];
    return climb(n, arr);
}

public int climb(int n, int[] arr){
    if (n == 0 || n == 1) {
        return 1;
    } else if(arr[n] > 0) {
        return arr[n];
    }
    arr[n] = climb(n-1, arr) + climb(n-2, arr);
    return arr[n];
}

在climb方法里判斷里，是要加上else if那個(gè)判斷的，目的是避免重復(fù)計(jì)算，不判斷的話就和第一種差不多了。

04 第三種解法

既然利用數(shù)組來存值，那么是不是可以省掉遞歸？直接拿數(shù)組元素返回結(jié)果就行。

public int climbStairs3(int n) {
    int[] arr = new int[n+1];
    arr[0] = 1;
    arr[1] = 1;
    for (int i=2; i<arr.length; i++) {
        arr[i] = arr[i-1]+arr[i-2];
    }
    return arr[n];
}

05 三種解法對比

為了驗(yàn)證哪種解法花費(fèi)的時(shí)間更少，編寫了一些簡易的測試代碼。

public static void main(String[] args) {
    Easy_070_ClimbingStairs instance = new Easy_070_ClimbingStairs();
    int arg = 44;
    long start = System.nanoTime();
    int result = instance.climbStairs(arg);
    long end = System.nanoTime();
    System.out.println("climbStairs---輸入："+arg+" , 輸出："+result+" , 用時(shí)："+(end-start)/1000+"微秒");
    System.out.println("----------------------------");
    long start2 = System.nanoTime();
    int result2 = instance.climbStairs2(arg);
    long end2 = System.nanoTime();
    System.out.println("climbStairs2---輸入："+arg+" , 輸出："+result2+" , 用時(shí)："+(end2-start2)/1000+"微秒");
    System.out.println("----------------------------");
    long start3 = System.nanoTime();
    int result3 = instance.climbStairs3(arg);
    long end3 = System.nanoTime();
    System.out.println("climbStairs3---輸入："+arg+" , 輸出："+result3+" , 用時(shí)："+(end3-start3)/1000+"微秒");
}

下面是運(yùn)行的結(jié)果

climbStairs---輸入：44 , 輸出：1134903170 , 用時(shí)：2795896微秒
----------------------------
climbStairs2---輸入：44 , 輸出：1134903170 , 用時(shí)：9微秒
----------------------------
climbStairs3---輸入：44 , 輸出：1134903170 , 用時(shí)：6微秒

可以看出來，第三種解法是最優(yōu)的，遞歸是好算法，但是會(huì)造成很多重復(fù)計(jì)算，影響速度，需要分場景來使用遞歸算法。

06 小結(jié)

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對我最大的回報(bào)和支持！