Skip to main content

10 斐波那契数列 & 跳台阶 & 矩形覆盖

斐波那契数列​

牛客

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

示例1
输入：4
返回值：3

斐波那契数列常用来做递归的例子。用递归做写起来简单，但是时间复杂度 (2n)，因为进行了大量重复计算。超过40后速度下降明显。 

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

正确的写法 

public class Solution {  
    public int Fibonacci(int n) {  
        if(n<=0) return 0;  
        if(n==1) return 1;  
        int pre1=0, pre2=1, fibN=0;  
        for(int i=1;i<n;++i){  
            fibN=pre1+pre2;  
            pre1=pre2;  
            pre2=fibN;  
        }  
        return fibN;  
    }  
}

跳台阶​

牛客

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

示例1
输入：2
返回值：2

示例2
输入：7
返回值：21

1级台阶有一种跳法，2级有两种。其它位置，要么从 n-1 跳上来，要么从 n-2 跳上来。同样是斐波那契数列 

public class Solution {  
    public int jumpFloor(int target) {  
        if(target<=0) return 0;  
        if(target<=2) return target;  
        int pre1=1,pre2=2,res=0;  
        for(int i=2;i<target;++i){  
            res=pre1+pre2;  
            pre1=pre2;  
            pre2=res;  
        }  
        return res;  
    }  
}

跳台阶扩展问题​

牛客

描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

示例1
输入：3
返回值：4

跳到第 n 级，可以从它前面的任意一级跳上来。

f(n)=f(n-1)+f(n-2)+...+f(1)+1
f(n-1)=f(n-2)+f(n-3)...+f(1)+1

两式联立，得 f(n)=2*f(n-1)。f(1)=1，所以 f(n)=2^(n-1) 

public class Solution {  
    public int jumpFloorII(int target) {  
        if(target<=0) return 0;  
        if(target<=2) return target;  
        return sq(target-1);  
    }  
      
    private int sq(int n) {  
        if (n == 1) return 2;  
        int next = sq(n / 2);  
        if (n % 2 == 1)  
            return next * next * 2;  
        return next * next;  
    }  
}

这样写更快 

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

矩形覆盖​

牛客

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

输入描述：
2*1的小矩形的总个数n

返回值描述：
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)

示例1
输入：0
返回值：0

示例2
输入：1
返回值：1

示例3
输入：4
返回值：5

n 为 1 时有 1 种覆盖方法， n 为 2 时有 2 种。当 n>2 时有 f(n)=f(n-1)+f(n-2) ，还是斐波那契数列 

public class Solution {  
    public int rectCover(int target) {  
        if(target<=0) return 0;  
        if(target<=2) return target;  
        int pre1=1, pre2=2, res=0;  
        for(int i=2;i<target;++i){  
            res=pre1+pre2;  
            pre1=pre2;  
            pre2=res;  
        }  
        return res;  
    }  
}