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

本文主要是介绍代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

  • 理论基础
  • 自己看到题目的第一想法
  • 看完代码随想录之后的想法

链接: 509. 斐波那契数
链接: 70. 爬楼梯
链接: 746. 使用最小花费爬楼梯

理论基础

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

自己看到题目的第一想法

509.斐波那契数:直接看题解。
70.爬楼梯:
746.使用最小花费爬楼梯:

看完代码随想录之后的想法

509.斐波那契数:
五部曲上秤!
(1)确定dp数组以及下标的含义:dp[i]的定义为:第i个数的斐波那契数值是dp[i]
(2)确定递推公式:直接有递推公式:状态转移方程dp[i]=dp[i-1]+dp[i-2]
(3)dp数组如何初始化:dp数组的初始化题目给了,dp[0]=0,dp[1]=1
(4)确定遍历顺序:从递归公式可以看出,dp[i]依赖dp[i-1]和dp[i-2],那么遍历顺序应当先确定前面的数再确定后面的数,所以是从前到后遍历。
(5)举例推导dp数组:根据递推公式推导举例,如果发现结果不对,就把dp数组打印出来看看推导的数列是否一致。
代码还是很简单的,可以使用
70.爬楼梯:
五部曲上秤!
(1)确定dp数组以及下标的含义:dp[i]的定义为:爬到第i层楼,有dp[i]种方法
(2)递推公式:dp[i]有两个方向可以推出来,dp[i-1]和dp[i-2],这里理解是一个难点,为什么可以这样推导,因为只能走1步或者2步,而没有其他方法上一步到这一步。所以dp[i]=dp[i-1]+dp[i-2]。
(3)dp数组如何初始化:dp[1]=1,dp[2]=2
(4)确定遍历顺序:从前向后遍历
(5)举例推导:如果代码有问题就把dp数组打印出来看与自己的举例是否一样。
746.使用最小花费爬楼梯:
五部曲上秤!
(1)确定dp数组以及下标的含义:dp[i]的定义为到位置i所需要的花费是多少。
(2)递推公式:有两个途径得到dp[i],一个是dp[i-1],一个是dp[i-2],有一个难想的点就是,究竟是从dp[i-1]跳还是从dp[i-2]跳呢?根据题意是需要最小的,那么就是dp[i]=min[dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。
(3)如何初始化:dp[0]=0, dp[1]=0
(4)遍历顺序:从前向后遍历
(5)举例推导

这篇关于代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1018853

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL中比较运算符的具体使用

《MySQL中比较运算符的具体使用》本文介绍了SQL中常用的符号类型和非符号类型运算符,符号类型运算符包括等于(=)、安全等于(=)、不等于(/!=)、大小比较(,=,,=)等,感兴趣的可以了解一下... 目录符号类型运算符1. 等于运算符=2. 安全等于运算符<=>3. 不等于运算符<>或!=4. 小于运

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)