剑指offer-JZ9

跳台阶扩展问题

https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

c++
考查斐波那契数列的变种,
第n级 = f[n-1]+f[n-2]+......f[0]
三种思路:暴力、递归、 动态规划、
思路一,暴力法:

class Solution {
public:
    int jumpFloorII(int number) {
        if (number ==0 || number==1) return 1;
        vector<int> f(number+1, 0);
        f[0]=1; 
        f[1]=1;
        for (int i =2; i<=number; i++){
            for (int j=0; j<i; j++){
                f[i]=f[i]+f[j];
            }
        }
       return f[number];
    }                            
};

继续优化:
第n级

第n-1级
图片说明
所以:
图片说明
图片说明
继续有一下推论:图片说明
应该是图片说明
暴力法2:

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;
        int ans=1;
        for(int i=2; i<=number; i++){
            ans = ans << 1;
        }
        return ans;
    }
};

或者直接计算:

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;
        return pow(2,number-1);
    }
};

思路二,递归法:

class Solution {
public:
    int jumpFloorII(int number) {
        if (number ==0 || number ==1) return 1;
        int ans = 0;
        while(number>=0){
            number--;
            ans = ans + jumpFloorII(number);
        }
        return ans;

    }
};

这里需要重复计算,因此加入记忆,存储已经计算过的;

class Solution {
public:
    int Fib(int n, vector<int> &dp){
        if (n==0 ||n==1) return 1;
        if (dp[n] != 0) return dp[n];
        int temp =n;
        while(temp>=0){
            temp--;
            dp[n]= dp[n] + Fib(temp, dp);
        }
        return dp[n];
    }
    int jumpFloorII(int number) {
        vector<int> dp(number+1, 0);
        return Fib(number, dp);
    }                            
};

递归法2,利用推导公式:

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;
        return jumpFloorII(number-1)*2;
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-11 21:41
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 22:26
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 13:45
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议