Q：n级台阶，每次只能上一级，或者两级。那么到第n级台阶一共有多少种走法。
思路：到第n级台阶的最后一步只有两种情况
1. 从第n-1级上去
2. 从第n-2级上去
也就是说，到第n级台阶走法可以当做从1到第n-1级的所有可能，加上从1到第n-2级的所有可
能。也就是 f(n) = f(n-1) + f(n-2)
同时可知初始条件 f(2) = 1; f(3) = 2
由这个思路，我们可以很自然地得出这样的代码
public static int f(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return f(n - 1) + f(n - 2);
}
这个解法看起来没什么问题，但是如果真的运行起来，很容易就会出现递归层数过多导致的StackOverflowError.所以这个解法并不能真的用来做计算。
如果不用递归，可以这样写 (参照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;
}
简单的测试：
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
*/
