青蛙跳台阶

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

思路：青蛙只能跳1或2，那么最后一个台阶和最后2个台阶的所有跳法加起来，就是n阶的所有跳法。

使用递归

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 1){
            return 1;
        }else if(number == 2){
            return 2;
        }else{
            return jumpFloor(number-1)+jumpFloor(number-2);
        }  
    }
};

View Code

不使用递归

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 1){
            return 1;
        }else if(number == 2){
            return 2;
        }
        int cur=2,last=1,result=0;
        for(int i=3; i<=number;i++){
            result = cur+last;
            last = cur;
            cur = result;
        }
        return result;
    }
};

View Code

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

思路：f(n)=f(1)+f(2)+....f(n-1)+1 跳到1级，跳2级，跳n-1级，之后在跳1次就能到n级了。直接跳n级。这些情况求和。

递归：

class Solution {
public:
    int jumpFloorII(int number) {

        if(number ==1){
            return 1;
        }else if(number ==2 ){
            return 2;
        }
        int sum =0;
        for(int i=1;i<number;i++){
            sum += jumpFloorII(i);
        }
        return sum+1;
    }
};

View Code

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)

不递归

class Solution {
public:
    int jumpFloorII(int number) {

        if(number ==1){
            return 1;
        }else if(number ==2 ){
            return 2;
        }
        vector<int >a(number+1);
        a[1]=1;
        a[2]=2;

        for(int i=1;i<=number;i++){
            for(int j=i;j>1;j--){
                a[i]+=a[j];
            }
        }
        return a[number];

    }
};

View Code

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1){
            return 1;
        }
        vector<int>a(number);
        a[0]=1;
        for(int i=1;i<number;i++){
            a[i]=2*a[i-1];
        }
        return a[number-1];
    }
};

View Code

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

思路：相当于青蛙跳台阶。最后一个（竖着放）和最后2个（横着放）。那么f(n)=f(n-1)+f(n-2)

原文链接: https://www.cnblogs.com/yuguangyuan/p/5882222.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/398134

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

青蛙跳台阶

相关推荐