【数据结构与算法】动态规划法解题20240227

在这里插入图片描述


动态规划法

  • 一、什么是动态规划
  • 二、动态规划的解题步骤
  • 三、509. 斐波那契数
    • 1、动规五部曲:
  • 四、70. 爬楼梯
    • 1、动规五部曲:
  • 五、746. 使用最小花费爬楼梯
    • 1、动规五部曲:

一、什么是动态规划

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的

二、动态规划的解题步骤

对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!
确定dp数组(dp table)以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

三、509. 斐波那契数

在这里插入图片描述

1、动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果
1、确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[i]

2、确定递推公式
为什么这是一道非常简单的入门题目呢?
因为题目已经把递推公式直接给我们了:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3、dp数组如何初始化
题目中把如何初始化也直接给我们了,如下:

dp[0] = 0;
dp[1] = 1;

4、确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

class S509:
    def func(self, n):
        # 1、创建dp数组,dp[i]:表示第i个数是第i个斐波那契数列
        dp = [0] * (n+1)
        # 3、初始化数组状态
        dp[0] = 0
        dp[1] = 1
        # 4、确定遍历顺序
        for i in range(2, n+1):
            # 2、确定递推公式
            dp[i] = dp[i - 1] + dp[i - 2]
        print(dp)
        return dp[n]


r = S509()
n = 4
print(r.func(n))

四、70. 爬楼梯

简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

在这里插入图片描述

1、动规五部曲:

1、确定dp数组以及下标的含义
dp[i]: 爬到第i层楼梯,有dp[i]种方法

2、确定递推公式
如何可以推出dp[i]呢?
从dp[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[i] = dp[i - 1] + dp[i - 2] 。
在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏。
这体现出确定dp数组以及下标的含义的重要性!
3、dp数组如何初始化
不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义。
4、确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的

class S70:
    def func(self, n):
        if n <= 1:
            return n
        # 1、创建dp数组,dp[i]:走到i台阶,一共用dp[i]种方法
        dp = [0] * (n + 1)
        # 3、数组初始化
        dp[1] = 1
        dp[2] = 2
        # 4、确定遍历顺序
        for i in range(3, n + 1):
            # 2、确定递推公式
            dp[i] = dp[i - 1] + dp[i - 2]
        print(dp)
        return dp[n]


r = S70()
n = 4
print(r.func(n))

五、746. 使用最小花费爬楼梯

简单
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
在这里插入图片描述

1、动规五部曲:

1、确定dp数组以及下标的含义
使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]。

2、确定递推公式
可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]。
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[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数组如何初始化
看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。
新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。
所以初始化 dp[0] = 0,dp[1] = 0;

4、确定遍历顺序
最后一步,递归公式有了,初始化有了,如何遍历呢?
因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

class S746:
    def func(self, cost):
        # 1、创建dp数组,dp[i]:走到楼梯i,需要最小的花费为dp[i]
        dp = [0] * (len(cost) + 1)
        # 3、初始化数组
        dp[0] = 0  # 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
        dp[1] = 0  # 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
        # 4、确定遍历顺序
        for i in range(2, len(cost) + 1):
            # 2、递推公式
            # 在第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)]


r = S746()
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(r.func(cost))

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/411384.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

23年中科院1区算法|长鼻浣熊优化算法COA原理及其利用与改进(Matlab/Python)

文章来源于我的个人公众号&#xff1a;KAU的云实验台&#xff0c;主要更新智能优化算法的原理、应用、改进 CEC2005中的测试 本文 KAU将介绍一个2023年1月发表在中科院1区KBS上的优化算法——长鼻浣熊优化算法(Coati Optimization Algorithm&#xff0c;COA)[1] 该算法由Dehg…

SpringBoot源码解读与原理分析(三十四)SpringBoot整合JDBC(三)声明式事务的传播行为控制

文章目录 前言10.5 声明式事务的传播行为控制10.5.1 修改测试代码&#xff08;1&#xff09;新建一个Service类&#xff0c;并引用UserService&#xff08;2&#xff09;修改主启动类 10.5.2 PROPAGATION_REQUIRED10.5.2.1 tm.getTransaction&#xff08;1&#xff09;获取事务…

IO进程线程作业day7

信号灯集共享内存 自定义头文件 #ifndef SEM_H_ #define SEM_H_ //创建信号灯集, int creat_t(int number); //申请释放资源 int P(int semid,int semno); //申请释放资源 int V(int semid,int semno); //删除信号灯集 int del(int semid); #endif信号灯集函数集合 #include…

物资管理新篇章:Java+SpringBoot实战

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

基于 ResNet50和 SVM + 决策树的人脸口罩检测

欢迎收看&#xff0c;这篇文章是关于我如何使用 ResNet50作为特征提取器来构建掩码检测&#xff0c;然后使用支持向量机(SVM) 决策树和叠加集成方法作为分类器的一个快速解释。 为了向研究人员致敬&#xff0c;这个应用程序是基于研究论文&#xff0c;题目是“在2019冠状病毒…

分布式应用:kylin 部署 zabbix 监控平台

目录 一、实验 1.环境 2. kylin 修改mysql数据库 3. kylin 部署 zabbix 监控平台 4. kylin 修改 zabbix 配置 5. kylin 修改zabbix web 二、问题 1. zabbix_server 查看版本报错 2.zabbix_server 文件如何去掉注释"#"和空行 3. zabbix图表显示异常 4.zabbi…

前端常见面试题之vue3

文章目录 1. vue3比vue2有哪些优势2. 描述vue3的生命周期3. 如何看待vue3中的Composition API 和 Options API4. 如何理解ref、 toRef、和toRefs?5. vue3升级了哪些功能6. Composition API如何实现代码逻辑的复用&#xff08;hook)7. Vue3如何实现响应式的8.Vue3使用Proxy对象…

2-22 方法、面向对象、类、JVM内存、构造方法

文章目录 方法的重载面向对象类、属性和方法成员变量默认值属性JVM简单内存分析栈空间堆空间 构造方法执行过程构造器注意点 方法的重载 一个类中名称相同&#xff0c;但是参数列表不同的方法 参数列表不同是指&#xff1a; 形参类型形参个数形参顺序 面向对象 field —— …

linux系统---防火墙拓展

目录 一、iptables 1.基本语法 2.四表五链——重点记忆 2.1四表 2.2五链 2.3总结 3.iptables选项示例 3.1 -Z 清空流量计数 3.2 -P 修改默认规则 3.3 -D 删除规则 3.4 -R 指定编号替换规则 4.白名单 5.通用匹配 6.示例 6.1添加回环网卡 6.2可以访问端口 6.3 主…

架构设计实践:熟悉架构设计方法论,并动手绘制架构设计图

文章目录 一、架构设计要素1、架构设计目标2、架构设计模式&#xff08;1&#xff09;分而治之&#xff08;2&#xff09;迭代式设计 3、架构设计的输入&#xff08;1&#xff09;概览&#xff08;2&#xff09;功能需求 - WH分析法&#xff08;3&#xff09;质量 - “怎么”分…

都说了别用BeanUtils.copyProperties,这不翻车了吧

分享是最有效的学习方式。 博客&#xff1a;https://blog.ktdaddy.com/ 故事 新年新气象&#xff0c;小猫也是踏上了新年新征程&#xff0c;自从小猫按照老猫给的建议【系统梳理大法】完完整整地梳理完毕系统之后&#xff0c;小猫对整个系统的把控可谓又是上到可一个新的高度。…

Arduino中安装ESP32网络抽风无法下载 暴力解决办法 python

不知道什么仙人设计的arduino连接网络部分&#xff0c;死活下不下来。&#xff08;真的沙口&#xff0c;第一次看到这么抽风的下载口&#xff09; 操作 给爷惹火了我踏马解析json选zip直接全部下下来 把这个大家的开发板管理地址下下来跟后面python放在同一目录下&#xff0c…

【Java程序设计】【C00317】基于Springboot的智慧社区居家养老健康管理系统(有论文)

基于Springboot的智慧社区居家养老健康管理系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的智慧社区居家养老健康管理系统设计与实现&#xff0c;本系统有管理员、社区工作人员、医生以及家属四种角色权限 管…

理解这几个安全漏洞,你也能做安全测试!

如今安全问题显得越来越重要&#xff0c;一个大型的互联网站点&#xff0c;你如果每天查看日志&#xff0c;会发现有很多尝试攻击性的脚本。 如果没有&#xff0c;证明网站影响力还不够大。信息一体化的背后深藏着各类安全隐患&#xff0c;例如由于开发人员的不严谨导致为Web应…

基于24扇区细分的三电平逆变器异步电机直接转矩控制系统学习

导读&#xff1a;本期文章介绍异步电机三电平24扇区的直接转矩控制。三电平逆变器直接转矩控制中&#xff0c;传统的PWM控制方法存在错判区间等问题。本文在借鉴三电平逆变器单一矢量及合成矢量的直接转矩控制研究和两电平12扇区直接转矩控制的基础上&#xff0c;将两电平12扇区…

堆/堆排序(C/C++)

本篇文章将会较为全面的介绍堆的概念以及实现堆两个重要算法&#xff1a;向上调整算法和向下调整算法。接着实现了堆排序。 若想查看对应位置&#xff0c;可直接按照以下目录进行查看&#xff1a; 目录 1.堆的概念及结构 2.堆的实现 2.1 堆的向上调整算法 2.2 堆的向下调整算法…

beego代理前端web的bug

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、beego代理前端web的bug总结 一、beego代理前端web的bug *报错&#xff0c;为web压缩包index.html里面的注释被错误解析&#xff0c;删掉就行 2024/02/22 10:2…

解析Hadoop三大核心组件:HDFS、MapReduce和YARN

目录 HadoopHadoop的优势 Hadoop的组成HDFS架构设计Yarn架构设计MapReduce架构设计 总结 在大数据时代&#xff0c;Hadoop作为一种开源的分布式计算框架&#xff0c;已经成为处理大规模数据的首选工具。它采用了分布式存储和计算的方式&#xff0c;能够高效地处理海量数据。Had…

蛇形矩阵1

题目描述 把数1&#xff0c;2&#xff0c;3&#xff0c;…&#xff0c;N*N按照“蛇形1”放入N*N的矩形中&#xff0c;输出结果。 下面是N10的蛇形1的图示 输入格式 第一行1个正整数&#xff1a;N&#xff0c;范围在[1,100]。 输出格式 N行&#xff0c;每行N个整数。 输入/…

docker下gitlab安装配置

一、安装及配置 1.gitlab镜像拉取 docker pull gitlab/gitlab-ce:latest2.运行gitlab镜像 docker run -d -p 443:443 -p 80:80 -p 222:22 --name gitlab --restart always --privilegedtrue -v /home/gitlab/config:/etc/gitlab -v /home/gitlab/logs:/var/log/gitlab -v …