面试题10：斐波那锲数列及其应用

现在要求输入一个整数n，请你输出斐波那契数列的第n项。
很明显递归解决：
从上往下递归，低效重复计算多
所以选择从下往上进行递归

public class Fibonacci {

    /**
     * 低效递归法
     */
    public int Fibonacci1(int n) {
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        return Fibonacci1(n-1) + Fibonacci1(n-2);
    }

    /**
     * 从下往上递归，相对高效，时间复杂度为o（n）
     */
    public int Fibonacci(int n) {
       int[] result = {0,1};
       if (n<2){
           return result[n];
       }
       int fn1 = 0,fn2 = 1,current = 0;
       for (int i=2;i<=n;i++){
           current = fn1+fn2;
           fn1 = fn2;
           fn2 = current;
       }
       return current;
    }

题型二：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。
* 求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：我们可以认为n级台阶，最后一跳可以选择跳一阶或者跳两阶，
* 如果跳一阶，则相当于前面n-1级台阶的跳法，跳两阶，则相当于前面n-2阶台阶的跳法
* 因此第n阶相当于n-1的跳法加上n-2的跳法
* 由于一个台阶只有一种跳法，两个台阶有两种跳法
* 类推下去

代码如下：

public int JumpFloor(int target) {
       if (target <=0){return 0;}
       if (target ==1){return 1;}
       if (target ==2){return 2;}
       int fn1=1,fn2=2,current=0;
       for (int i=3;i<=target;i++){
           current = fn1 + fn2;
           fn1 = fn2;
           fn2 = current;

       }
       return current;
    }

题型3：上述题目改成青蛙可以一次跳一到n级台阶，问有多少种可能？
f（0）= 0
f（1）= 1
f（2）= f（1）+f（0）= f(2-1) + f(2-2)
f（3）= f(3-1) + f(3-2) + f(3-3)
......
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）;

public int JumpFloorII(int target) {
        if (target <=0){return 0;}
        if (target == 1){return 1;}
        int fn = 0,fn1=1;
        for (int i=2;i<=target;i++){
            fn = 2*fn1;
            fn1 = fn;
        }
        return fn;
    }

    /**
     * fn=2^n-1
     * @param target
     * @return
     */

    public int JumpFloorII0(int target) {
        if (target <=0){return 0;}
        return (int)Math.pow(2,target-1);
    }

    /**
     * 由上到下的递归
     * @param target
     * @return
     */
    public int JumpFloorII1(int target) {
        if (target <=0){return 0;}
        if (target == 1){return 1;}
        return 2*JumpFloorII1(target-1);
    }

题型三：
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：例如我们把当前覆盖方法计为f（n），小矩形有两种覆盖方式，第一种竖着覆盖，则为后面n-1个覆盖的方法，第二种横着覆盖，则下面也需要一个矩形，后面还剩n-2个矩形；所以可得f（n）= f（n-1）+f（n-2） n>2;
f(1) = 1；f（2）= 2；

/**
     * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
     * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
     * @param target
     * @return
     */
    public int RectCover(int target) {
       if (target <= 0){return 0;}
       if (target == 1){return 1;}
       if (target == 2){return 2;}
       int current=0,fn1=1,fn2=2;
       for (int i=3;i<=target;i++){
           current = fn1 + fn2;
           fn1 = fn2;
           fn2 = current;
       }
       return current;
    }

    /**
     * 通过减法获得原来的改变后的和，少用一个变量
     * @param target
     * @return
     */
    public int RectCover0(int target) {
        if (target <= 0) {
            return 0;
        }
        if (target == 1) {
            return 1;
        }

        int a = 1;
        int b = 2;
        while (target > 1) {
            b = a + b;
            a = b - a;
            target--;
        }
        return a;
    }