题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39
int Fibonacci(int n) { // 递归 if(n < 0) return 0; else if(n == 1 || n == 2) return 1; else if(n >2 && n <= 39) { return Fibonacci(n-1) + Fibonacci(n-2); } else return 0; } //您的代码已保存 运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。case通过率为0.00% int Fibonacci(int n) { if(n<=0) return 0; if(n==1 || n==2) return 1; int f1 = 1; int f2 =1; int f3; for(int i =3; i<=n;i++) { f3 = f1+f2; f1 = f2; f2 = f3; } return f3; }总结：递归重复的代码太多，时间复杂度是O(nlogn)，而下面第二种的解法是O(n)。
题目二：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 分析：如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳法了：一种是分两次跳，每次跳1级；另外是一次跳2级。接着我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择： 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)； 另一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)； 因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2);
int jumpFloor(int number) { if(number <= 0) return 0; else if(number == 1) return 1; else if(number == 2) return 2; else { return jumpFloor(number-1) + jumpFloor(number-2); } }题目三：变态跳台阶：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 n = 1时，只有1种跳法，f(1) = 1 n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2) n = 3时，会有三种跳得方式，1阶、2阶、3阶， 那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3) ，因此结论是f(3) = f(3-1)+f(3-2)+f(3-3) n = n时，会有n中跳的方式，1阶、2阶…n阶，当n时，第一次跳的时候就有多种不同的选择： 第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)； 第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)； 第一次跳3级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-3)； …… 第一次跳n-1级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(1)； 第一次跳n级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(0)； f(n) = f(n-1)+f(n-2)+…+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + … + f(n-1) 6) 由以上已经是一种结论，但是为了简单，我们可以继续简化： f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1) = f(n-1) + f(n-1) 可以得出： f(n) = 2*f(n-1)
int jumpFloorII(int number) { if(number <=0) return 0; else if(number == 1) { return 1; }else { return 2 * jumpFloorII(number - 1); } }