剑指offer--递归

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
递归实现,时间复杂度为O(2^n)：

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1) return n;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

时间复杂度为O(n)
代码：

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1) return n;
        int first = 0;
        int second = 1;
        int fib = 0;
        for(int i = 2;i<=n;i++){
            fib = first + second;
            first = second;
            second = fib;
        }
        return fib;
    }
}

public class Solution {
    public int JumpFloor(int target) {
        int a = 1, b = 1;
        for (int i = 1; i < target; i++) {
            a = a + b;
            b = a - b;
        }
        return a;
    }
}

题目二：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
分析：
到n阶，可以从n-1阶跳1步，也可以从n-2阶跳两步，所以:
f(n) = f(n-1) + f(n-2)

就是斐波那契问题，代码同题目一

题目三：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
跳到n阶 ，可以从n-1阶再跳1步，n-2阶再跳2步....从第1阶再跳n-1步，从第0阶再跳n步，所以：
f(n) = f(n-1) + f(n-2) +...+f(1)+f(0);同理
f(n-1) = f(n-2) +...+f(1)+f(0)；
两式相减 ，得到 f(n) = 2f(n-1) (n>=2) f(0) =1;

代码为

public class Solution {
    public int JumpFloorII(int target) {
        if(target==0||target==1) return target;
        int res=1;
        for(int i=2;i<=target;i++){
            res = res*2;
        }
        return res;
    }
}

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

image.png

解析：

image.png