草庐IT

LeetCode动态规划经典题目（九）：入门

Jomo. 2023-07-25 原文

学习目标：

了解动态规划

学习内容：

 1. LeetCode509. 斐波那契数https://leetcode.cn/problems/fibonacci-number/

 2. LeetCode70. 爬楼梯https://leetcode.cn/problems/climbing-stairs/

 3. LeetCode746. 使用最小花费爬楼梯https://leetcode.cn/problems/min-cost-climbing-stairs/

学习产出：

能够独立解决上面三道入门级动态规划题

1. LeetCode509. 斐波那契数

1.动态规划
class Solution {
public:
    int fib(int n) {
        //边界情况
        if(n<0){
            return -1;
        }
        if(n==0){
            return 0;
        }

        //dp[i]=F(i)
        vector<int>dp(n+1);//0~n，n+1个数

        //转移方程：F(n)=F(n-1)+F(n-2)
        //所以先初始化F(1),F(0)
        dp[0]=0;
        dp[1]=1;

        //完善动态规划表
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};
2.动态规划
完善动态规划表的时候发现，只需要前两个数即可，所以我们只需要三个变量即可。
空间复杂度从O(n)->O(1)
class Solution {
public:
    int fib(int n) {
        if(n<0){
            return -1;
        }

        int a=0;//F(0)
        int b=1;//F(1)
        int c=a+b;//F(2)
        while(n--){
            c=a+b;
            a=b;
            b=c;
        }
        //在while循环中，相当于a/b/c都往后移了n个数
        //所以最终a：F(n)，b：F(n+1)，c：F(n+2)
        return a;
    }
};
可能很多人不理解为什么返回a而不是c，其实只要代入一个案例进去算就明白了

2. LeetCode70. 爬楼梯

1.动态规划表：
class Solution {
public:
    int climbStairs(int n) {
        //边界情况
        if(n<1){
            return 0;
        }
        if(n==1){
            return 1;
        }
        
        //dp[i]：到达i阶楼梯的方法数
        vector<int>dp(n+1);//有dp[n]
        dp[1]=1;
        dp[2]=2;
        //完善动态规划表
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};
2.动态规划：我们仍只需维护三个变量即可
class Solution {
public:
    int climbStairs(int n) {
        //边界情况
        if(n<1){
            return 0;
        }
        if(n==1){
            return 1;
        }
        //注意要用long，不然c可能会溢出
        long a=1;//F(1)
        long b=2;//F(2)
        long c=a+b;//F(3)
        n-=1;//a往后(n-1)个数才是F(n)，所以n变成n-1
        while(n--){
            c=a+b;
            a=b;
            b=c;
        }
        return a;
    }
};

3. LeetCode746. 使用最小花费爬楼梯

1.动态规划表
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        //dp[i]：爬'到'第i阶楼梯所需最低费用
        vector<int>dp(n+1);

        //初始化dp，可以从下标为0或1的台阶开始爬楼梯
        dp[0]=0;//从下标为0开始
        dp[1]=0;//从下标为1开始
        
        //完善dp
        for(int i=2;i<=n;i++){
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};
2.动态规划：只需维护三个变量
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int a=0;
        int b=0;
        int c=0;
        for(int i=2;i<=cost.size();i++){
            //a是台阶更低的所需费用，所以和cost[i-2]搭配
            c=min(a+cost[i-2],b+cost[i-1]);
            a=b;
            b=c;
        }
        //i向后移n-2位，c初始为F(2)，结束循环后刚好是F(n)
        return c;
    }
};

LeetCode入门class61linkc++算法动态规划数据结构

有关LeetCode动态规划经典题目（九）：入门的更多相关文章

  1. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  2. LC滤波器设计学习笔记（一）滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称

  3. 微信小程序开发入门与实战（Behaviors使用） - 2

    @作者:SYFStrive @博客首页:HomePage📜：微信小程序📌：个人社区（欢迎大佬们加入）👉：社区链接🔗📌：觉得文章不错可以点点关注👉：专栏连接🔗💃：感谢支持,学累了可以先看小段由小胖给大家带来的街舞👉微信小程序（🔥）目录自定义组件-behaviors    1、什么是behaviors    2、behaviors的工作方式    3、创建behavior    4、导入并使用behavior    5、behavior中所有可用的节点    6、同名字段的覆盖和组合规则总结最后自定义组件-behaviors    1、什么是behaviorsbehaviors是小程序中，用于实现

  4. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

  5. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  6. ES基础入门 - 2

    ES一、简介1、ElasticStackES技术栈：ElasticSearch：存数据+搜索；QL；Kibana：Web可视化平台，分析。LogStash：日志收集，Log4j:产生日志；log.info(xxx)。。。。使用场景：metrics：指标监控…2、基本概念Index（索引）动词：保存（插入）名词：类似MySQL数据库，给数据Type（类型）已废弃，以前类似MySQL的表现在用索引对数据分类Document（文档）真正要保存的一个JSON数据{name:"tcx"}二、入门实战{"name":"DESKTOP-1TSVGKG","cluster_name":"elasticsear

  7. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  8. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  9. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  10. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

随机推荐