You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Note : Given n will be a positive integer.
本題對(duì)應(yīng)于《劍指offer》P75的跳臺(tái)階問題：
一只青蛙一次可以跳上1級(jí)臺(tái)階刻盐，也可以跳上2級(jí)蹬刷。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法罢坝。
首先我們考慮最簡(jiǎn)單的情況。如果只有1級(jí)臺(tái)階橡庞，那顯然只有一種跳法荸频。如果有2級(jí)臺(tái)階戏仓，那就有兩種跳法了：一種是分兩次跳疚宇，每次跳1級(jí)；另外一種就是一次跳2級(jí)赏殃。
接著我們?cè)賮碛懻撘话愕那闆r敷待。把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)f(n)。當(dāng)n>2時(shí)嗓奢，第一次跳的時(shí)候有兩種不同的選擇：
- 第一次只跳1級(jí)讼撒，此時(shí)跳上n級(jí)臺(tái)階的跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即f(n-1)
- 第一次跳2級(jí)，此時(shí)跳上n級(jí)臺(tái)階的跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目根盒，即f(n-2)
因此n級(jí)臺(tái)階的不同跳法的總數(shù) f(n) = f(n-1) + f(n-2)
上面的分析過程钳幅，我們用到了動(dòng)態(tài)規(guī)劃的方法，找到了狀態(tài)轉(zhuǎn)移方程炎滞，不難看出這實(shí)際上就是一個(gè)類斐波那契數(shù)列敢艰，只是初始條件與傳統(tǒng)的斐波那契數(shù)列略有不同，這里f(2)=2册赛。
關(guān)于斐波那契數(shù)列钠导，我在之前的文章中已經(jīng)詳細(xì)分析了這類問題的三種計(jì)算機(jī)解法：自上而下的遞歸實(shí)現(xiàn)太耗時(shí)，轉(zhuǎn)化為特征矩陣的乘方又太復(fù)雜森瘪，所以一般使用自底向上的迭代算法牡属。
應(yīng)用自底向上的迭代算法求解本題的源碼如下，其時(shí)間復(fù)雜度為O(n)
public class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int fibCurrent = 0, fibOneBack = 2, fibTwoBack = 1;
for (int i = 3; i <= n; i++) {
fibCurrent = fibOneBack + fibTwoBack;
fibTwoBack = fibOneBack;
fibOneBack = fibCurrent;
}
return fibCurrent;
}
}
系統(tǒng)準(zhǔn)備一個(gè)函數(shù)扼睬，是常數(shù)項(xiàng)時(shí)間復(fù)雜度比較大的事情逮栅，而且系統(tǒng)遞歸棧的大小也是有限的，所以工程上的代碼窗宇，很少使用遞歸措伐。對(duì)于一種算法的遞歸版本，往往可以通過自己維護(hù)一個(gè)棧或者迭代的方式军俊，將其改寫成非遞歸版本進(jìn)行優(yōu)化侥加。
《劍指offer》上還對(duì)本題進(jìn)行了如下擴(kuò)展
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2 級(jí)粪躬，……担败，也可以跳上n級(jí)，此時(shí)該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法镰官？
首先我們?nèi)匀豢紤]最簡(jiǎn)單的情況氢架。如果只有1級(jí)臺(tái)階，那顯然只有一種跳法朋魔。如果有2級(jí)臺(tái)階，那就有兩種跳法了：一種是分兩次跳卿操，每次跳1級(jí)警检；另外一種就是一次跳2級(jí)。
接著我們?cè)賮碛懻撘话愕那闆r害淤。把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)f(n)扇雕。當(dāng)n>2時(shí)，第一次跳的時(shí)候有n種不同的選擇：
- 第一次只跳1級(jí)窥摄，此時(shí)跳上n級(jí)臺(tái)階的跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目镶奉，即f(n-1)；
- 第一次跳2級(jí)，此時(shí)跳上n級(jí)臺(tái)階的跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目哨苛，即f(n-2)鸽凶；
- 第一次跳3級(jí)，此時(shí)跳上n級(jí)臺(tái)階的跳法數(shù)目等于后面剩下的n-3級(jí)臺(tái)階的跳法數(shù)目建峭，即f(n-3)玻侥；
- ......；
- 第一次跳n-1級(jí)亿蒸，此時(shí)跳上n級(jí)臺(tái)階的跳法數(shù)目等于后面僅剩的1級(jí)臺(tái)階的跳法數(shù)目凑兰，即f(1)；
- 從初始位置直接跳n級(jí)边锁，這也對(duì)應(yīng)了一種跳法
綜上所述姑食，n級(jí)臺(tái)階的不同跳法的總數(shù) f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + 1
把n-1帶入上面的遞推式得 f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1
所以最終的遞推式為 f(n) = 2 * f(n-1)
應(yīng)用自底向上的迭代算法求解本題的源碼如下：
public class Solution {
public int climbStairs(int n) {
int result = 1;
if (n == 1) {
return result;
}
for (int i = 2; i <= n; i++) {
result *= 2;
}
return result;
}
}