1. n级台阶问题

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
*/