斐波那契数列&&变形题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

这个问题很简单，若是用递归可能效率会很低，重复计算太多。

因此我们使用非递归自下而上计算，代码如下：

class Solution {
public:
    int Fibonacci(int n) {
        int f0=0;
        int f1=1;
        if(n==0)
            return f0;
        if(n==1)
            return f1;
        int fibN=0;
        for(int i=2;i<=n;i++)
        {
            fibN=f0+f1;
            f0=f1;
            f1=fibN;
        }
        return fibN;
    }
};      

变形题目

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

对于本题，只有一次 1阶或者2阶的跳法。

（1）如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)；

（2）假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)

（3）由上可假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)

（4）通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

（5）可以发现最终得到如下表达式，

1, (n=1)  
     f(n) =  2, (n=2)  
             f(n-1)+f(n-2) ,(n>2,n为整数)      

代码如下：

class Solution {
public:
    int jumpFloor(int number) {
        if(number==0)
            return 0;
        else if(number==1)
            return 1;
        else if(number==2)
            return 2;
        int f1=1;
        int f2=2;
        int sum=0;
        for(int i=3;i<=number;i++)
        {
            sum=f1+f2;
            f1=f2;
            f2=sum;
        }
        return sum;
    }
};      

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

和上题不一样的是，n个台阶会有一次n阶的跳法。分析如下:

（1）n = 1时，只有1种跳法，f(1) = 1

（2) n = 2时，会有两个跳的方式，一次1阶或者2阶，f (2) = f(2-1) + f(2-2)

（3) 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)

（4) n = n时，会有n中跳的方式，1阶、2阶…n阶，得出结论：

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)

（5) 为了简单，我们可以继续简化：

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)      

（6) 得出最终结论，在n阶台阶，一次有1、2、…n阶的跳的方式时，总的跳法为：

1 ,(n=0 )  
  f(n) =   1 ,(n=1 ) 
           2*f(n-1),(n>=2)      

代码如下：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0)
            return 0;
        if(number==1)
            return 1;
        return 2*jumpFloorII(number-1);
    }
};      

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

class Solution {
public:
    int rectCover(int number) {
        if(number<=0)
            return 0;
        if(number==1)
            return 1;
        if(number==2)
            return 2;
        return rectCover(number-1)+rectCover(number-2);
    }
};