LeetCode刷题第五天(动态规划)(填坑中)

举报
开心星人 发表于 2022/06/29 23:07:13 2022/06/29
【摘要】 1137. 第 N 个泰波那契数 使用递归会超时,用动态规划 class Solution { public: int tribonacci(int n) { //动态规划一般需要开...

1137. 第 N 个泰波那契数
在这里插入图片描述
使用递归会超时,用动态规划

class Solution {
public:
    int tribonacci(int n) {
    	//动态规划一般需要开数组
        int arr[n+1];
        arr[0]=0;
        if(n>=1){
            arr[1]=1;
        }
        if(n>=2){
            arr[2]=1;
        }
        for(int i=3;i<n+1;i++){
            arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
        }
        return arr[n];
    }
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

70. 爬楼梯
在这里插入图片描述
想要到达第n阶,需要从第n-1或者第n-2阶跳上去只有这两种可能。所以 F[n]=F[n-1]+F[n-2]

class Solution {
public:
    int climbStairs(int n) {
        int arr[n+1];
        arr[0]=0;
        if(n>=1){
            arr[1]=1;
        }
        if(n>=2){
            arr[2]=2;
        }
        for(int i=3;i<n+1;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

746. 使用最小花费爬楼梯
在这里插入图片描述

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        int arr[n+1];
        arr[0]=0;
        if(n>=1){
            arr[1]=0;
        }
        for(int i=2;i<n+1;i++){
            arr[i]=min(arr[i-1]+cost[i-1],arr[i-2]+cost[i-2]);
        }
        return arr[n];
    }
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

198. 打家劫舍
在这里插入图片描述

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        int arr[n];
        arr[0]=nums.at(0);
        if(n>1){
            arr[1]=max(nums.at(0),nums.at(1));
        }
        for(int i=2;i<n;i++){
            arr[i]=max(arr[i-1],nums.at(i)+arr[i-2]);
        }
        return arr[n-1];
    }
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

文章来源: blog.csdn.net,作者:开心星人,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/qq_55675216/article/details/122582313

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。