当前位置: 首页 > news >正文

代码随想录算法训练营第三十八天|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

题目:理论基础

文章链接:代码随想录

 视频链接:动态规划理论基础

动态规划五部曲:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

 题目:509. 斐波那契数

文章链接:代码随想录

视频链接:LeetCode:509.斐波那契数

题目链接:力扣题目链接

图释:

class Solution {
public:// 确定dp数组(dp table)以及下标的含义 vector<int> dp, dp[i]表示第n哥斐波那契数 // 确定递推公式      dp[i]=dp[i-1]+dp[i-2]// dp数组如何初始化  dp[0]=1, dp[1]=1// 确定遍历顺序      从前往后// 举例推导dp数组    int fib(int n) {if(n<=0)return 0;if(n==1) return 1;vector<int> dp(n+1);dp[0]=0;dp[1]=1;for(int i=2; i<=n; i++){//从2开始,直到第n个数dp[i]= dp[i-1]+dp[i-2];}return dp[n];}
};
class Solution {
public:int traversal(int n){// 终止条件if(n==1) return 1;if(n==0) return 0;// 递归return traversal(n-1)+traversal(n-2);}  int fib(int n) {  return traversal(n);}
};再精简
class Solution {
public:int fib(int n) {  // 终止条件if(n==1) return 1;if(n==0) return 0;return fib(n-1)+fib(n-2);}
};

题目:70. 爬楼梯

文章链接:代码随想录

视频链接:LeetCode:70.爬楼梯

题目链接:力扣题目链接

图释:

class Solution {
public:// 确定dp数组(dp table)以及下标的含义 vector<int> dp, dp[i]表示达到第n层楼梯需要的方法 // 确定递推公式      dp[i]=dp[i-1]+dp[i-2]// dp数组如何初始化  dp[1]=1, dp[2]=2// 确定遍历顺序      从前往后// 举例推导dp数组  // 题目中要求的每次可以爬1或者2个台阶,也就是说,最终到达n阶台阶有两种方式,// 一个是爬1阶台阶到达(对应的是从n-1阶台阶开始)// 另一个就是爬2阶台阶到达(对应的是从n-2阶台阶开始爬),// 而爬n-1阶和n-2阶台阶的方法有dp[n-1],dp[n-2]个// 所以最终爬n阶台阶的方法种类就是dp[n-1]+dp[n-2]int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;vector<int> dp(n+1);dp[1]=1;dp[2]=2;for(int i=3; i<=n; i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
};
class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;return climbStairs(n-1)+climbStairs(n-2);}
};  //超时

题目:746. 使用最小花费爬楼梯

文章链接:代码随想录

视频链接:LeetCode:746.使用最小花费爬楼梯

题目链接:力扣题目链接

图释:

class Solution {
public:// 确定dp数组(dp table)以及下标的含义 vector<int> dp, dp[i]表示爬到第n层台阶的最低花费// 确定递推公式      dp[i]= min(dp[i-1]+cost[i-1], dp[i-2]+cost[i+2]) 可以选择从前一个台阶或者前两个台阶爬上来 // dp数组如何初始化  dp[0]=0, dp[1]=0  题目说了,可以选择从0或者1台阶出发,也就是dp[i]到这两个台阶的最低花费为0// 确定遍历顺序      从前往后// 举例推导dp数组 int minCostClimbingStairs(vector<int>& cost) {if(cost.size()==0 || cost.size()==1) return 0;vector<int> dp(cost.size()+1);dp[0]=dp[1]=0;for(int i=2; i<=cost.size(); i++){  // 顶楼表示为dp[n] dp[i]= min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}return dp[cost.size()];}
};

相关文章:

代码随想录算法训练营第三十八天|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

题目&#xff1a;理论基础 文章链接&#xff1a;代码随想录 视频链接&#xff1a;动态规划理论基础 动态规划五部曲&#xff1a; 确定dp数组&#xff08;dp table&#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 题目&#xff1a;509. 斐…...

大数据开发之Hadoop(优化新特征)

第 1 章&#xff1a;HDFS-故障排除 注意&#xff1a;采用三台服务器即可&#xff0c;恢复到Yarn开始的服务器快照。 1.1 集群安全模块 1、安全模式&#xff1a;文件系统只接收读数据请求&#xff0c;而不接收删除、修改等变更请求 2、进入安全模式场景 1&#xff09;NameNod…...

在使用go语言开发的时候,程序启动后如何获取程序pid

在Go语言中&#xff0c;标准库并没有直接提供获取进程ID&#xff08;PID&#xff09;的函数。通常&#xff0c;你可以使用os包和syscall包来调用底层的操作系统函数来获取PID。 以下是一个获取程序PID的示例代码&#xff1a; package mainimport ("fmt""os&qu…...

HFSS笔记/信号完整性分析(二)——软件仿真设置大全

文章目录 1、多核运算设置1.1 如何设置1.2 如何查看自己电脑的core呢&#xff1f;1.3 查看求解的频点 2、求解模式设置Driven Terminal vs Driven modal 3、Design settings4、自适应网格划分5、更改字体设置 仅做笔记整理与分享。 1、多核运算设置 多核运算只对扫频才有效果&…...

mysql主从报错:Last_IO_Error: Error connecting to source解决方法

目录 报错 处理方法 1.从库停止同步 2.主库修改my.cnf 生效配置default-authentication-pluginmysql_native_password 3.重启服务重新创建复制用户 4.重新同步 5.测试主从 报错 Last_IO_Error: Error connecting to source repl_user192.168.213.15:3306. This was atte…...

AOI与AVI:在视觉检测中的不同点和相似点

AOI&#xff08;关注区域&#xff09;和AVI&#xff08;视觉感兴趣区域&#xff09;是视觉检测中常用的两个概念&#xff0c;主要用于识别和分析图像或视频中的特定区域。虽然这两个概念都涉及到注视行为和注意力分配&#xff0c;但它们在定义和实际应用等方面有一些差异。 AOI…...

Python爬虫 - 网易云音乐下载

爬取网易云音乐实战&#xff0c;仅供学习&#xff0c;不可商用&#xff0c;出现问题&#xff0c;概不负责&#xff01; 分为爬取网易云歌单和排行榜单两部分。 因为网页中&#xff0c;只能显示出歌单的前20首歌曲&#xff0c;所以仅支持下载前20首歌曲&#xff08;非VIP音乐&…...

yarn包管理器在添加、更新、删除模块时,在项目中是如何体现的

技术很久不用&#xff0c;就变得生疏起来。对npm深受其害&#xff0c;决定对yarn再整理一遍。 yarn包管理器 介绍安装yarn帮助信息最常用命令 介绍 yarn官网&#xff1a;https://yarn.bootcss.com&#xff0c;学任何技术的最新知识&#xff0c;都可以通过其对应的网站了解。无…...

React实现Intro效果(基础简单)

下载&#xff1a;利用Intro.js实现简单的新手引导 npm install intro.js --save yarn add intro.js 第一步&#xff1a;在我们需要引导的页面引入 import introJs from intro.js; import intro.js/introjs.css; //css是下载成功后就有的 第二步&#xff1a;在组件页面 c…...

HBuilderx发布苹果的包需要注意什么

在HBuilderX中发布苹果的包&#xff0c;需要注意以下几点&#xff1a; 开发者账号注册&#xff1a;在发布应用到App Store之前&#xff0c;需要先注册一个苹果开发者账号。注册过程较为繁琐&#xff0c;需要提供个人信息并支付年费。应用标识和证书&#xff1a;在发布iOS应用之…...

烟火检测/周界入侵/视频智能识别AI智能分析网关V4如何配置ONVIF摄像机接入

AI边缘计算智能分析网关V4性能高、功耗低、检测速度快&#xff0c;易安装、易维护&#xff0c;硬件内置了近40种AI算法模型&#xff0c;支持对接入的视频图像进行人、车、物、行为等实时检测分析&#xff0c;上报识别结果&#xff0c;并能进行语音告警播放。算法可按需组合、按…...

C++ 内联函数

C 内联函数是通常与类一起使用。如果一个函数是内联的&#xff0c;那么在编译时&#xff0c;编译器会把该函数的代码副本放置在每个调用该函数的地方。 对内联函数进行任何修改&#xff0c;都需要重新编译函数的所有客户端&#xff0c;因为编译器需要重新更换一次所有的代码&a…...

微信小程序带参数分享界面、打开界面加载分享内容

分享功能是微信小程序常用功能之一&#xff0c;带参分享和加载可以让分享对象打开界面时看到和分享内容。 带参分享 用户点击微信小程序右上角自带分享&#xff0c;或者点击自定义分享按钮进行分享时&#xff0c;可在onShareAppMessage函数定义分享行为。 分享界面路径可带参…...

中小企业选择CRM系统有哪些注意事项?如何高效实施CRM

阅读本文&#xff0c;你将了解&#xff1a;一、中小型企业对CRM系统的主要需求&#xff1b;二、CRM系统实施策略和优秀实践。 在快速变化的商业环境中&#xff0c;中小型企业面临着独特的挑战&#xff1a;如何在有限的资源下高效地管理客户关系、提升销售效率&#xff0c;保持…...

轮胎侧偏刚度线性插值方法

一、trucksim取数据 步骤一 步骤二 二、数据导入到matlab中 利用simulink的look up table模块 1是侧偏角&#xff1b;2是垂直载荷&#xff1b;输出是侧向力。 侧向力除以侧偏角就是实时的侧偏刚度。...

前端JS代码中Object类型数据的相关知识

获取Object类型数据的方式有两种&#xff1a; 方括号获取&#xff1a;Object["arg1"]点获取&#xff1a;Object.arg1 前端遍历Object类型数据的方式 遍历JavaScript中的对象有几种方法&#xff0c;包括使用for…in循环、Object.keys()方法、Object.values()方法和…...

vue基于Spring Boot共享单车租赁报修信息系统

共享单车信息系统分为二个部分&#xff0c;即管理员和用户。该系统是根据用户的实际需求开发的&#xff0c;贴近生活。从管理员处获得的指定账号和密码可用于进入系统和使用相关的系统应用程序。管理员拥有最大的权限&#xff0c;其次是用户。管理员一般负责整个系统的运行维护…...

CentOS 6.10 安装图解

特特特别的说明 CentOS发行版已经不再适合应用于生产环境&#xff0c;客观条件不得不用的话&#xff0c;优选7.9版本&#xff0c;8.5版本次之&#xff0c;最次6.10版本&#xff08;比如说Oracle 11GR2就建议在6版本上部署&#xff09;&#xff01; 引导和开始安装 选择倒计时结…...

Web自动化测试中的接口测试

1、背景 1.1 Web程序中的接口 1.1.1 典型的Web设计架构 web是实现了基于网络通信的浏览器客户端与远程服务器进行交互的应用&#xff0c;通常包括两部分&#xff1a;web服务器和web客户端。web客户端的应用有html&#xff0c;JavaScript&#xff0c;ajax&#xff0c;flash等&am…...

轻松识别Midjourney等AI生成图片,开源GenImage

AIGC时代&#xff0c;人人都可以使用Midjourney、Stable Diffusion等AI产品生成高质量图片&#xff0c;其逼真程度肉眼难以区分真假。这种虚假照片有时会对社会产生不良影响&#xff0c;例如&#xff0c;生成公众人物不雅图片用于散播谣言&#xff1b;合成虚假图片用于金融欺诈…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...