70.爬樓梯
假設(shè)你正在爬樓梯。需要 階你才能到達樓頂规脸。
每次你可以爬 或
個臺階沽一。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 是一個正整數(shù)答姥。
示例 1：
輸入：
輸出：
解釋： 有兩種方法可以爬到樓頂铣除。
階 +
階
示例 2：
輸入：
輸出：
解釋： 有三種方法可以爬到樓頂。
解答1
此題目可以說是最經(jīng)典（另一種說法是最“容易”）的動態(tài)規(guī)劃的題目鹦付。
動態(tài)規(guī)劃是將一個大問題分解為多個簡單的子問題來求解的方法尚粘。
動態(tài)規(guī)劃常常適用于有重疊子問題與最優(yōu)子結(jié)構(gòu)的問題。
思路
- 設(shè)
為總的方法數(shù)量
- 可以看到敲长，到第
階的方法其實一共有兩種方式
- 從第
階爬一步到達第
- 從第
階爬兩步到達第
- 從第
- 因此可以總結(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雖然勉強能跑月褥，但是有一個非常嚴重的問題是弛随，重復(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);
}
}
