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

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

目录

509.斐波那契数

动态规划五部曲:

        1.确定dp数组(dp table)以及下标的含义

        2.确定递推公式

        3.dp数组如何初始化

        4.确定遍历顺序

        5.举例推导dp数组

70.爬楼梯

动态规划五部曲:

        1.确定dp数组(dp table)以及下标的含义

        2.确定递推公式

        3.dp数组如何初始化

        4.确定遍历顺序

        5.举例推导dp数组

746.使用最小花费爬楼梯

动态规划五部曲:

        1.确定dp数组(dp table)以及下标的含义

        2.确定递推公式

        3.dp数组如何初始化

        4.确定遍历顺序

        5.举例推导dp数组


509.斐波那契数

题目链接:509. 斐波那契数 - 力扣(LeetCode)

动态规划五部曲:

        1.确定dp数组(dp table)以及下标的含义

                dp[i]表示第i项斐波那契数列

        2.确定递推公式

                第i项斐波那契数列 = 前两项之和,即dp[i] = dp[i-1] + dp[i-2];

        3.dp数组如何初始化

                递推公式的i = 0和i = 1不符合递推公式,且是最边界情况,特别处理,

         即dp[0] = 0,dp[1] = 1;

        4.确定遍历顺序

                从第三个数据位置开始遍历

        5.举例推导dp数组

                dp[2]、dp[3]符合,递推到dp[...]都可行

class Solution 
{
public:int fib(int n) {vector<int> dp(n+10);dp[0] = 0;dp[1] = 1;for(int i=2; i<=n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

70.爬楼梯

题目链接:70. 爬楼梯 - 力扣(LeetCode)

动态规划五部曲:

        1.确定dp数组(dp table)以及下标的含义

                dp[i]表示第i个台阶的方案数

        2.确定递推公式

               1阶:1

                2阶:2

                3阶:先走一步,如果一步走一阶,剩2阶,方案数为2,

                        如果一步走两阶,剩1阶方案数为1,方案数总共2+1 = 3

                4阶:先走一步,如果一步走一阶,剩3阶,方案数为3,

                        如果一步走两阶,剩2阶方案数为2,方案数总共3+2 = 5

                5阶:先走一步,如果一步走一阶,剩4阶,方案数为5,

                        如果一步走两阶,剩3阶方案数为3,方案数总共5+3 = 8

                总结:当前台阶i的方案数 = i-1台阶方案数 +i-2台阶方案数

                即,dp[i] = dp[i-1] + dp[i-2]

        3.dp数组如何初始化

                递推公式的i = 1和i = 2不符合递推公式,且是最边界情况,特别处理,

         即dp[1] = 1,dp[2] = 2;

        4.确定遍历顺序

                从第三个数据位置开始遍历

        5.举例推导dp数组

                第二步推到过了可行。

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+10);dp[1] = 1;dp[2] = 2;for(int i=3; i<=n; i++){dp[i] = dp[i-1] + dp[i-2];	// i-1台阶的方案数 +i-2台阶的方案数 }   return dp[n];}
};

746.使用最小花费爬楼梯

题目链接:746. 使用最小花费爬楼梯 - 力扣(LeetCode)

动态规划五部曲:

        1.确定dp数组(dp table)以及下标的含义

                dp[i]表示到达第i个台阶所花的最小费用

        2.确定递推公式

                0阶:0元。

                1阶:0元。

                2阶:min(到达(2-1)阶的费用+(2-1)阶跳的费用 , 到达(2-2)阶的费用 +(2-2)阶跳的费用)。

                3阶:min(到达(3-1)阶的费用+(3-1)阶跳的费用 , 到达(3-2)阶的费用 +(3-2)阶跳的费用)。

                4阶:min(到达(4-1)阶的费用+(4-1)阶跳的费用 , 到达(4-2)阶的费用 +(4-2)阶跳的费用)。

                整体看感觉思路可行:即,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

        3.dp数组如何初始化

                第0阶和第1阶的为起点,不需要花费价钱,故dp[0] = 0, dp[1] = 0。

        4.确定遍历顺序

                从第三个数据位置开始遍历

        5.举例推导dp数组

                按预期,数据是从第0个台阶依次到第n个台阶(顶点)的变化,所以数据是递推过去的,担心min()可能取0的值,验证了i = 2的程序,和i = 3的清楚,数据按预测的递推过程进行变化,可行。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+10);dp[0] = 0;dp[1] = 0;int n = cost.size();for(int i=2; i<=n; i++){// i-1往上爬 或者i-2往上爬,取最小dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]); // 通过这个输出+题目信息把"<n"改成了"<=n",了解到n-1是台阶,而不是到顶// cout<<dp[i]<<' '<<dp[i-1]+cost[i-1]<<' '<<dp[i-2]+cost[i-2]<<'\n';   }return dp[n];}
};

相关文章:

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

目录 509.斐波那契数 动态规划五部曲&#xff1a; 1.确定dp数组&#xff08;dp table&#xff09;以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 70.爬楼梯 动态规划五部曲&#xff1a; 1.确定dp数组&#xff08;dp table&#xff09;…...

【2024年华为OD机试】 (A卷,100分)- 总最快检测效率(Java JS PythonC/C++)

一、问题描述 题目描述 在系统、网络均正常的情况下组织核酸采样员和志愿者对人群进行核酸检测筛查。 每名采样员的效率不同&#xff0c;采样效率为 N 人/小时。由于外界变化&#xff0c;采样员的效率会以 M 人/小时为粒度发生变化&#xff0c;M 为采样效率浮动粒度&#xf…...

【大数据】Apache Superset:可视化开源架构

Apache Superset是什么 Apache Superset 是一个开源的现代化数据可视化和数据探索平台&#xff0c;主要用于帮助用户以交互式的方式分析和展示数据。有不少丰富的可视化组件&#xff0c;可以将数据从多种数据源&#xff08;如 SQL 数据库、数据仓库、NoSQL 数据库等&#xff0…...

LabVIEW调用不定长数组 DLL数组

在使用 LabVIEW 调用 DLL 库函数时&#xff0c;如果函数中的结构体包含不定长数组&#xff0c;直接通过 调用库函数节点&#xff08;Call Library Function Node&#xff09; 调用通常会遇到问题。这是因为 LabVIEW 需要与 DLL 中的数据结构完全匹配&#xff0c;而包含不定长数…...

MySQL 17 章——触发器

在实际开发中&#xff0c;我们经常会遇到这样的情况&#xff1a;有2个或者多个相关联的表&#xff0c;比如商品信息表和库存信息表&#xff0c;分别存放在两个不同的数据表中&#xff0c;我们在添加一条新商品记录的时候&#xff0c;为了保证数据的完整性&#xff0c;必须同时在…...

面向对象分析与设计Python版 面向对象设计方法

文章目录 前言一、职责驱动设计二、职责驱动设计-案例 前言 面向对象设计目标&#xff1a;在面向对象分析建立的领域模型的基础上&#xff0c;定义对象操作&#xff08;职责&#xff09;。为对象分配职责的方法有&#xff1a; 职责驱动设计遵循GRASP设计原则&#xff08;Gene…...

GB/T 19582.1-2008主要内容

标准背景与概述 GB/T 19582.1-2008是由中国国家标准化管理委员会发布的国家标准&#xff0c;旨在指导和规范基于Modbus协议的工业自动化网络的设计和实施。该标准由全国工业过程测量控制和自动化标准化技术委员会&#xff08;TC124&#xff09;归口&#xff0c;并由中国机械工…...

[石榴翻译] 维吾尔语音识别 + TTS语音合成

API网址 丝路AI平台 获取 Access token 接口地址&#xff1a;https://open.xjguoyu.cn/api/auth/oauth/token&#xff0c;请求方式&#xff1a;GET&#xff0c;POST Access token是调用服务API的凭证&#xff0c;调用服务API之前需要获取 token。每次成功获取 token 以后只有…...

算法题(32):三数之和

审题&#xff1a; 需要我们找到满足以下三个条件的所有三元组&#xff0c;并存在二维数组中返回 1.三个元素相加为0 2.三个元素的下标不可相同 3.三元组的元素不可相同 思路&#xff1a; 混乱的数据不利于进行操作&#xff0c;所以我们先进行排序 我们可以采取枚举的方法进行解…...

webpack03

什么是source-map 将代码编译压缩之后&#xff0c;&#xff0c;可以通过source-map映射会原来的代码&#xff0c;&#xff0c;&#xff0c;在调试的时候可以准确找到原代码报错位置&#xff0c;&#xff0c;&#xff0c;进行修改 source-map有很多值&#xff1a; eval &#…...

组会 | SNN 的 BPTT(backpropagation through time)

目录 1 神经学基础知识1.1 神经元1.2 神经元之间的连接1.3 膜电位1.4 去极化与超极化 2 SNN2.1 LIF 模型2.2 BPTT 中存在的问题2.3 梯度爆炸或消失问题 前言&#xff1a; 本博仅为组会总结&#xff0c;如有谬误&#xff0c;请不吝指正&#xff01;虽然标题为 BPTT&am…...

CDA数据分析师一级经典错题知识点总结(3)

1、SEMMA 的基本思想是从样本数据开始&#xff0c;通过统计分析与可视化技术&#xff0c;发现并转换最有价值的预测变量&#xff0c;根据变量进行构建模型&#xff0c;并检验模型的可用性和准确性。【强调探索性】 2、CRISP-DM模型Cross Industry Standard Process of Data Mi…...

django基于Python的电影推荐系统

Django 基于 Python 的电影推荐系统 一、系统概述 Django 基于 Python 的电影推荐系统是一款利用 Django 框架开发的智能化应用程序&#xff0c;旨在为电影爱好者提供个性化的电影推荐服务。该系统通过收集和分析用户的观影历史、评分数据、电影的属性信息&#xff08;如类型…...

JVM与Java体系结构

一、前言: Java语言和JVM简介: Java是目前最为广泛的软件开发平台之一。 JVM:跨语言的平台 随着Java7的正式发布&#xff0c;Java虚拟机的设计者们通过JSR-292规范基本实现在Java虚拟机平台上运行非Java语言编写的程序。 Java虚拟机根本不关心运行在其内部的程序到底是使用何…...

网络授时笔记

SNTP的全称是Simple Network Time Protocol&#xff0c;意思是简单网络时间协议&#xff0c;用来从网络中获取当前的时间&#xff0c;也可以称为网络授时。项目中会使用LwIP SNTP模块从服务器(pool.ntp.org)获取时间 我们使用sntp例程&#xff0c;sntp例程路径为D:\Espressif\…...

【CSS】HTML页面定位CSS - position 属性 relative 、absolute、fixed 、sticky

目录 relative 相对定位 absolute 绝对定位 fixed 固定定位 sticky 粘性定位 position&#xff1a;relative 、absolute、fixed 、sticky &#xff08;四选一&#xff09; top&#xff1a;距离上面的像素 bottom&#xff1a;距离底部的像素 left&#xff1a;距离左边的像素…...

spark汇总

目录 描述运行模式1. Windows模式代码示例 2. Local模式3. Standalone模式 RDD描述特性RDD创建代码示例&#xff08;并行化创建&#xff09;代码示例&#xff08;读取外部数据&#xff09;代码示例&#xff08;读取目录下的所有文件&#xff09; 算子DAGSparkSQLSparkStreaming…...

【Rust自学】11.5. 在测试中使用Result<T, E>

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 11.5.1. 测试函数返回值为Result枚举 到目前为止&#xff0c;测试运行失败的原因都是因为触发了panic&#xff0c;但可以导致测试失败的…...

Sping Boot教程之五十四:Spring Boot Kafka 生产者示例

Spring Boot Kafka 生产者示例 Spring Boot 是 Java 编程语言中最流行和使用最多的框架之一。它是一个基于微服务的框架&#xff0c;使用 Spring Boot 制作生产就绪的应用程序只需很少的时间。Spring Boot 可以轻松创建独立的、生产级的基于 Spring 的应用程序&#xff0c;您可…...

设计模式-结构型-组合模式

1. 什么是组合模式&#xff1f; 组合模式&#xff08;Composite Pattern&#xff09; 是一种结构型设计模式&#xff0c;它允许将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端对单个对象和组合对象的使用具有一致性。换句话说&#xff0c;组合模式允…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

深度解析云存储:概念、架构与应用实践

在数据爆炸式增长的时代&#xff0c;传统本地存储因容量限制、管理复杂等问题&#xff0c;已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性&#xff0c;成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理&#xff0c;云存储正重塑数据存储与…...

2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】

1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...