递归系列

问题一：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0），n<=39。给出一个非递归代码。

class Solution {
public:
    int Fibonacci(int n) {
        //用循环不用递归
        if(n<2)
            return n;
        int a=0;
        int b=1;
        int result;
        for(int i=1;i<n;i++)
        {
            result=a+b;
            a=b;
            b=result;
        }
       return result;
    }
};

问题2：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

分析：当n<=2时，跳法是等于n的，当n大于3时，假定第一次跳1级，那么剩下还有n-1阶，假定第一次跳2级，那么剩下还有n-2阶，因此得到递归公式：f(n)=f(n-1)+f(n-2)。

代码：

class Solution {
public:
    int jumpFloor(int number) { 
        if(number<3)
            return number;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

问题3：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析＋代码：

class Solution {
public:
    int jumpFloorII(int number) {
        /*分析：跳3阶以下时，跳法和阶数相同，f(1)=1,f(2)=2，跳3阶时，考虑到可能出现直接跳3阶
        故f(3)=f(1)+f(2)+f(0)(第一次跳2阶，第一次跳1阶，第一次跳3阶)，以此类推
        f(4)=f(3)+f(1)+f(2)+f(0)=2f(3),f(5)=2f(4)=4f(3),以此类推*/
          if(number<3) return number;
          int sum=4;
          for(int i=3;i<number;i++)
          {
              sum+=sum;
          }
        return sum;
    }
};

问题四：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法。

代码：

class Solution {
public:
    int rectCover(int number) {
        //斐波那切数列，这里方法应该不按顺序，比如n=3时，就是1+2这么考虑，不认为2+1是另一种情况
        if(number<3)
            return number;
        return rectCover(number-1)+rectCover(number-2);
    }
};