70.爬樓梯

假設(shè)你正在爬樓梯。需要 階你才能到達(dá)樓頂。

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

注意：給定 是一個正整數(shù)。

示例 1：

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

1. 階 + 階
2. 階

示例 2：

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

1. 階 + 階 + 階
2. 階 + 階
3. 階 + 階

解答1

此題目可以說是最經(jīng)典（另一種說法是最“容易”）的動態(tài)規(guī)劃的題目。
動態(tài)規(guī)劃是將一個大問題分解為多個簡單的子問題來求解的方法。
動態(tài)規(guī)劃常常適用于有重疊子問題與最優(yōu)子結(jié)構(gòu)的問題。

思路

1. 設(shè)為總的方法數(shù)量
2. 可以看到，到第階的方法其實一共有兩種方式
   • 從第階爬一步到達(dá)第階
   • 從第階爬兩步到達(dá)第階
3. 因此可以總結(jié)出公式
   可以發(fā)現(xiàn)，這個就是斐波那契數(shù)列的變種。

代碼1

java實現(xiàn)

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

代碼非常的簡潔，馬上丟到leetcode上跑一次，居然執(zhí)行了10801 ms。擊敗了0.98%的人。。。

解法2

解法1雖然勉強(qiáng)能跑，但是有一個非常嚴(yán)重的問題是，重復(fù)計算量過大。
但是因為并沒有暫存的地方，導(dǎo)致被計算了兩次。
此時考慮到以往的數(shù)據(jù)會被重復(fù)使用，那么何不做一個數(shù)組暫存數(shù)據(jù)呢。

代碼2

java實現(xiàn)

class Solution {
    public int climbStairs(int n) {
        int[] cache = new int[n+1];
        return resolve(n);
    }
    public int resolve(int n, int[] cache) {
        if (n==1) {
            return 1;
        }
        if (n==2) {
            return 2;
        }
        if (cache[n] ==0) {
            cache[n] = resolve(n-1,cache) +resolve(n-2,cache);
        }
        return cache[n];
    }
}

此方法4ms執(zhí)行完成。

解法3

上述兩種方法，均是遞歸調(diào)用，如何轉(zhuǎn)為迭代呢？

代碼3

java實現(xiàn)

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