代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
文章目录
- 代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
- 理论基础
- 一、常规题目
- 二、解题步骤
- 509. 斐波那契数
- 一、动态规划v1
- 二、动态规划v2
- 三、动态规划v3
- 70. 爬楼梯
- 一、动态规划v1
- 二、动态规划v2
- 746. 使用最小花费爬楼梯
- 一、dp v1
- 二、dp v2
理论基础
一、常规题目

二、解题步骤
对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
题目链接
- 确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[i]- 确定递推公式
状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];- dp数组如何初始化
题目中把如何初始化也直接给我们了,如下: dp[0] = 0; dp[1] = 1;- 确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的- 打印dp数组
一、动态规划v1
class Solution:def fib(self, n):# 排除 Corner Caseif n == 0:return 0# 创建 dp table dp = [0] * (n + 1)# 初始化 dp 数组dp[0] = 0dp[1] = 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n + 1):# 确定递归公式/状态转移公式dp[i] = dp[i - 1] + dp[i - 2]# 返回答案return dp[n
二、动态规划v2
class Solution:def fib(self, n):if n<=1:return ndp=[0,1]for i in range(2,n+1):total = dp[0]+dp[1]dp[0]=dp[1]dp[1]=total return total
三、动态规划v3
class Solution:def fib(self, n):if n<=1:return nprev0,prev1 = 0,1for _ in range(2,n+1):cur = prev0 + prev1prev0,prev1 = prev1,curreturn cur
70. 爬楼梯
题目链接
- 确定dp数组以及下标的含义
dp[i]的定义为:爬到第i层楼梯,有dp[i]种方法- 确定递推公式
dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。
dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么
状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];- dp数组如何初始化
dp[1] = 1; dp[2] = 2;- 确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的- 打印dp数组
一、动态规划v1
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""dp = [0]*(n+1)if n <=2:return ndp[1]=1dp[2]=2for i in range(3,n+1):dp[i]=dp[i-1]+dp[i-2]return dp[n]
二、动态规划v2
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""dp=[0,1,2]if n <=2:return nfor i in range(3,n+1):total = dp[1]+dp[2]dp[1]=dp[2]dp[2]=totalreturn total
746. 使用最小花费爬楼梯
题目链接
- 确定dp数组以及下标的含义
dp[i]的定义为:到达第i台阶所花费的最少体力为dp[i]- 确定递推公式
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]
状态转移方程 : dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);- dp数组如何初始化
dp[0] = 0; dp[1] = 0;- 确定遍历顺序
因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了- 打印dp数组
一、dp v1
class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""dp = [0] * (len(cost) + 1)dp[0] = 0 # 初始值,表示从起点开始不需要花费体力dp[1] = 0 # 初始值,表示经过第一步不需要花费体力for i in range(2, len(cost) + 1):# 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步# 选择其中花费体力较小的路径,加上当前步的花费,更新dp数组dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)] # 返回到达楼顶的最小花费
二、dp v2
class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""dp0=0dp1=0for i in range(2,len(cost)+1):dp2=min(dp1+cost[i-1],dp0+cost[i-2])dp0=dp1dp1=dp2return dp2
相关文章:
代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 文章目录 代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯理论基础一、常规题目二、解题步骤…...
CSS拟物按钮
<div class"btn">F</div>.btn {margin: 150px 0 0 150px;display: flex;justify-content: center;align-items: center;width: 100px;height: 100px;background-color: #fff;border-radius: 20px;font-size: 50px;color: #333;/* 禁止选中文本 */user-se…...
websevere服务器从零搭建到上线(三)|IO多路复用小总结和服务器的基础框架
文章目录 epollselect和poll的优缺点epoll的原理以及优势epoll 好的网络服务器设计Reactor模型图解Reactor muduo库的Multiple Reactors模型 epoll select和poll的优缺点 1、单个进程能够监视的文件描述符的数量存在最大限制,通常是1024,当然可以更改数…...
解决宝塔Nginx和phpMyAdmin配置端口冲突问题
问题描述 在对基于宝塔面板的 Nginx 配置文件进行端口修改时,我注意到 phpMyAdmin 的端口配置似乎也随之发生了变化! 解决方法 官方建议在处理 Nginx 配置时,应避免直接修改默认的配置文件,以确保系统的稳定性和简化后续的维护…...
光伏EPC管理软件都有哪些功能和作用?
光伏EPC管理软件是用于光伏工程项目管理的综合性工具,它涵盖了从项目策划、设计、采购、施工到运维的各个环节。 1、项目总览 管理所有项目计划,包括项目类型、项目容量等。 调整和优化项目计划,以应对不可预见的情况。 2、施工管理 制定…...
BGP学习一:关于对等体建立和状态组改变
目录 一.BGP基本概念 (1).BGP即是协议也是分类 1.早期EGP 2.BGP满足不同需求 3.BGP区域间传输的优势 (1)安全性——只传递路由信息 (2)跨网段建立邻居 4.BGP总结 5.BGP的应用 (1&#…...
ETL工具kettle(PDI)入门教程,Transform,Mysql->Mysql,Csv->Excel
什么是kettle,kettle的下载,安装和配置:ETL免费工具kettle(PDI),安装和配置-CSDN博客 mysql安装配置:Linux Centos8 Mysql8.3.0安装_linux安装mysql8.3-CSDN博客 1 mysql -> mysql 1.1 mysql CREATE TABLE user_…...
常见地图坐标系间的转换算法JavaScript实现
文章目录 🍉 不同的地图厂商使用不同的坐标系来表示地理位置。以下简述:🍉 前置常量和方法:🍉 BD-09转GCJ-02(百度转谷歌、高德)🍉 GCJ-02转BD-09(谷歌、高德转百度)🍉 WGS84转GCJ-02(WGS84转谷歌、高德)🍉 GCJ-02转WGS84(谷歌、高德转WGS84)🍉 BD-09转wgs84坐…...
基于python的大麦网自动抢票工具的设计与实现
基于python的大麦网自动抢票工具的设计与实现 Design and Implementation of Da Mai Net Ticket Grabbing tool based on Python 完整下载链接:基于python的大麦网自动抢票工具的设计与实现 文章目录 基于python的大麦网自动抢票工具的设计与实现摘要第一章 引言1.1 研究背景…...
2024年5月树莓集团快讯
树莓集团近期快讯 1 园区专场招聘会进校园 国际数字影像产业园联合四川城市职业学院的专场招聘会成功召开,共计提供400余个工作岗位。 2 园区硬件优化再升级 园区硬件优化再升级,智能门禁系统及人脸识别系统下周投入使用。 3 基地短剧合作交流 天府…...
网站localhost和127.0.0.1可以访问,本地ip不可访问解决方案
部署了一个网站, 使用localhost和127.0.0.1加端口号可以访问, 但是使用本机的ip地址加端口号却不行. 原因可能有多种. 可能的原因: 1 首先要确认是否localhost对应的端口是通的(直接网址访问), 以及你无法访问的那个本机ip是否正确(使用ping测试); 2 检查本机的防火…...
Docker Dockerfile如何编写?
Dockerfile 是一个用来构建镜像的文本文件,文本内容包含了一条条构建镜像所需的指令和说明。 1.指令说明 FROM,构建镜像基于哪个镜像 MAINTAINER,镜像维护者姓名或邮箱地址 RUN,构建镜像时运行的指令 CMD,运行容器时执…...
Python数独游戏
数独(Sudoku)是一种逻辑性的数字填充游戏,玩家需要在一个分为九宫的81格网格上填入数字,同时满足每一行、每一列以及每个宫(3x3的子网格)的数字都不重复。 在Python中实现一个数独游戏可以涉及到多个方面&…...
24 | MySQL是怎么保证主备一致的?
MySQL 主备的基本原理 内部流程 备库 B 跟主库 A 之间维持了一个长连接。主库 A 内部有一个线程,专门用于服务备库 B 的这个长连接。一个事务日志同步的完整过程是这样的: 在备库 B 上通过 change master 命令,设置主库 A 的 IP、端口、用户名、密码,以及要从哪个位置开始…...
2.数据类型与变量(java篇)
目录 数据类型与变量 数据类型 变量 整型变量 长整型变量 短整型变量 字节型变量 浮点型变量 双精度浮点型 单精度浮点型 字符型变量 布尔型变量(boolean) 类型转换 自动类型转换(隐式) 强制类型转换(显式) 类型提升 字符串类型 数据类…...
QT设计模式:桥接模式
基本概念 桥接模式是一种结构型设计模式,它将抽象部分与它的实现部分分离,使得它们可以独立地变化,而不会相互影响。 需要实现的结构如下: 抽象部分(Abstraction):定义了抽象类的接口&#x…...
简单粗暴的翻译英文pdf
背景:看书的时候经常遇到英文pdf,没有合适的翻译软件可以快速翻译全书。这里提供一个解决方案。 Step 1 打开英文pdfCTRLA全选文字CTRLC复制打开记事本CTRLV复制保存为data.txt Step 2 写一个C脚本 // ToolPdf2Html.cpp : 此文件包含 "main&quo…...
UDP和TCP协议比较,TOE技术
如今在某些方面TCP超越UDP的主要原因如下 在硬件层面的TOE(TCP Offload Engine)功能,将越来越多的TCP功能卸载到网卡上。它极大地提升了TCP的性能,使其在高吞吐量场景下的表现更为出色。近年TCP的拥塞控制算法实现了显著进步。这些新算法显著提高了TCP在…...
第十三节 huggingface的trainner解读与Demo
文章目录 前言一、trainer和TrainingArguments训练与预测完整Demo1、数据构建2、TrainingArguments构建3、Trainer初始化4、模型训练5、模型推理6、完整demo代码7、完整运行结果二、辅助函数1、yield返回内容2、迭代器中断恢复迭代demo3、yield from结构4、torch.Generator()的…...
GO: json 处理
需要引入"encoding/json"包 json解析到map jsonStr : "{\"a\":\"test\",\"b\":\"testb\"}" var dat map[string]string err : json.Unmarshal([]byte(jsonStr), &dat) if err nil {fmt.Println(dat) }结果…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
