要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
解法一：递归解法，但递归解法有很严重的效率问题，因为递归解法中重复的计算太多。
解法二：循环实现，避免重复计算，把已经得到的数列中间项保存起来。
public class Solution { public int Fibonacci(int n) { if(n <= 0) return 0; if(n == 1) return 1; int a = 0, b = 1, sum = 0; for(int i = 2; i< n; i++){ sum = a + b; a = b; b = sum; } return a + b; } }
斐波那契数列的应用
青蛙跳台阶问题
一只青蛙一次可以跳上一阶台阶，也可以跳上二阶台阶，求该青蛙跳上一个N阶的台阶总共有多少种跳法。
扩展：
一只青蛙一次可以跳上一阶台阶，也可以跳上两阶......也可以跳上N阶，此刻该青蛙跳上一个N阶的台阶共有多少种跳法？