Q：n級(jí)臺(tái)階暮顺，每次只能上一級(jí)厅篓，或者兩級(jí)。那么到第n級(jí)臺(tái)階一共有多少種走法捶码。
思路：到第n級(jí)臺(tái)階的最后一步只有兩種情況
1. 從第n-1級(jí)上去
2. 從第n-2級(jí)上去
也就是說(shuō)羽氮，到第n級(jí)臺(tái)階走法可以當(dāng)做從1到第n-1級(jí)的所有可能，加上從1到第n-2級(jí)的所有可
能惫恼。也就是 f(n) = f(n-1) + f(n-2)
同時(shí)可知初始條件 f(2) = 1; f(3) = 2
由這個(gè)思路档押，我們可以很自然地得出這樣的代碼
public static int f(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return f(n - 1) + f(n - 2);
}
這個(gè)解法看起來(lái)沒(méi)什么問(wèn)題，但是如果真的運(yùn)行起來(lái)，很容易就會(huì)出現(xiàn)遞歸層數(shù)過(guò)多導(dǎo)致的StackOverflowError.所以這個(gè)解法并不能真的用來(lái)做計(jì)算令宿。
如果不用遞歸叼耙，可以這樣寫(xiě) (參照SICP)
public static int f2(int n) {
int a = 0;
int b = 0;
for (int i = 0; i <= n; i++) {
if (i == 0) {
a = 0;
continue;
}
if (i == 1) {
a = 1;
b = 0;
continue;
}
a = a + b;
b = a - b;
}
return a;
}
簡(jiǎn)單的測(cè)試：
public static void main(String[] args) {
for(int i=0; i<=5; i++) {
System.out.println(i + " steps : " + f2(i) + " ways");
}
}
/*
Test Results：
0 steps : 0 ways
1 steps : 1 ways
2 steps : 1 ways
3 steps : 2 ways
4 steps : 3 ways
5 steps : 5 ways
*/
