著名的Fibonnaci数列相关的问题经常在面试中遇到。要解决这种问题需要两步：
1，确定遇到的问题是斐波那契数列。这是解决问题的关键点。
2，解决这个数列问题。
下面用实例说明：
问题一
一个人上台阶，一次可以上一级台阶，也可以一次上两级台阶。问，上n级台阶有多少种走法？
解决思路
1，首先我们可以简单计算一下1~4级台阶的上法分别是
1,2,3,5
看到这几项，我们已经可以往斐波那契数列怀疑了。但我们不可能计算出所有的数值，只能总结出一般规律，才能确定这到底是不是斐波那契数列。
2，所以一般性规律，就是上n级台阶的方法和n-1级台阶的方法之间的关联性。
再次思考上台阶的问题，可以得到一个显而易见的结论：
一个人要上到第n级，有两个选择：
- 上到n-2级台阶以后，一次跨两级来到第n级台阶。这里不再考虑两次跨一级来到n级台阶了，因为这种方法和下面到n-1级台阶的方法部分重合了。
- 上到n-1级台阶以后，一次跨一级来到第n级台阶。
因此问题已经非常清楚：n级台阶的上法等于上n-2级台阶的方法总数+上n-1级台阶的上法总数。
毫无疑问这就是Fibonnaci数列。
3，确定是Fibonnaci数列后，要解决就非常简单了。如使用递归：
public static long Fib1(int n){
if (n==1)
return 1;
if (n==2)
return 2;
return Fib1(n-1)+Fib1(n-2);
}
而Fibonnaci数列的通项公式就是：F(n)=F(n-1)+F(n-2)。由此可以看到数列的通项公式和递归算法之间的直接联系。
问题二
现在延伸一下上面的问题
一个人上台阶，一次可以上一级台阶，也可以一次上两级台阶，也可以一次上三级台阶。问，上n级台阶有多少种走法？
显而易见这是Fibonnaci数列的变种，通项公式应该是：
F(n)=F(n-1)+F(n-2)+F(n-3)
还是用递归解决。