剑指offer-7,8,9,10-斐波那契数列 试读

思路

7,8,9,10的思路都是一样的
F(n)=F(n-1)+F(n-2)

• 递归：占内存，容易栈溢出
• 动态规划,一维数组保存前面所有状态，又由于本题只与前两个状态有关，所以用两个变量保存前两个状态即可

第7题

动态规划

public class Solution {
    public int Fibonacci(int n) {
        if(n<=0){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        int p=1,q=1;
        for(int i=3;i<=n;i++){
            q=p+q;
            int temp=p;
            p=q;
            q=temp;
        }
        return p;
    }
}

递归,本题n较小，也OK

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

第8题 青蛙跳台阶，跳1，2步台阶

public class Solution {
    public int JumpFloor(int target) {
        if(target<=1){
            return 1;
        }
        int[] ints=new int[target+1];
        ints[0]=1;
        ints[1]=1;
        for(int i=2;i<ints.length;i++){
            ints[i]=ints[i-1]+ints[i-2];
        }
        return ints[target];
    }
}

第9题 变态跳台阶，可以跳1，2，3...n步台阶

F(n)=F(n-1)+...+F(0),F(0)=1,F(1)=1
进一步归纳，可以发现，F(n)=2*F(n-1),n>=2;

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

        return sum;
    }
}

第10题 矩形覆盖

public class Solution {
    public int RectCover(int target) {
        if(target<=2){
            return target;
        }
        int[] res=new int[target+1];
        res[0]=0;
        res[1]=1;
        res[2]=2;
        for(int i=3;i<res.length;i++){
            res[i]=res[i-1]+res[i-2];
        }
        return res[target];
    }
}