算法:动态规划的入门理解
文章目录
- 算法原理
- 题目解析
- 第n个泰波那契数列
- 三步问题
- 使用最小花费爬楼梯
从本篇开始总结的是动态规划的一些内容,动态规划是算法中非常重要的一个版块,因此也是学习算法中的一个重点,在学习动态规划前应当要把动态规划的基础知识学习一下
算法原理
动态规划既然是一个新的算法,这个名字也是新名字,那么就要首先明确这个算法的名字代表什么含义
动态规划是什么?
动态规划其实就是dp表
中的值所表示的含义
那什么又是dp表?
dp表
是解决这类问题中必须要使用的一个内容,通常是借助vector
来表示
dp表怎么写出来?
一般来说题目要求中会有一些提示,同时在分析问题的过程中,如果遇到了分析的过程中有重复的子问题,也可以借助这个逻辑写出一个状态转移方程,利用这个状态转移方程就可以填写到dp表
中
状态转移方程
状态转移方程就是在动态规划中根据一部分提示找到dp表
的填入方法,再根据这个方法就可以借助dp表
解决问题,因此状态转移方程是解决问题的关键
题目解析
首先用一个比较简单的题目来上手动态规划
第n个泰波那契数列
对于这个题来说,可以用上面的动态规划的方法来处理:
首先创建一个dp表
,再从题目中找到状态转移方程,再利用状态转移方程写入dp表
,再利用dp表
求出要找的数据
class Solution
{
public:int tribonacci(int n) {// 处理边界if(n==0){return 0;}if(n==1 || n==2){return 1;}// 创建dp表vector<int> dp(n+1);// 初始化dp表dp[0]=0;dp[1]=1;dp[2]=1;//填入dp表for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}// 返回值return dp[n];}
};
三步问题
分析问题:
假设现在有1个台阶,那么小孩跳到这个台阶的方法有1种,直接从地面走到第一个台阶上
假设现在有2个台阶,那么小孩跳到这个台阶的方法有2种,第一种从地面直接走到第二个台阶上,第二种是小孩从地面走到第一个台阶,再从第一个台阶走到第二个台阶上
假设现在有3个台阶,那么小孩跳到这个台阶的方法有4种,第一种直接跳到第三个台阶上,第二种先跳到第一个台阶,再从第一个台阶向第三个台阶跳,而从第一个台阶向第三个台阶跳又有两种,参考有2个台阶的方案,那么总共第二种方法有2种,第三种小孩跳到第二个台阶,再从第二个台阶跳到第三个台阶,因此总共有四种方法
假设现在有4个台阶,那么小孩跳到第四个台阶的方法总共有7种,先让小孩走到第一个台阶,再从第一个台阶走到第四个台阶即可,而小孩走到第一个台阶的方法有1种;也可以先让小孩走到第二个台阶,再从第二个台阶走到第四个台阶,而小孩走到第二个台阶的方法有2种;先让小孩走到第三个台阶,再从第三个台阶直接到第四个台阶,而直接让小孩走到第四个台阶的方法有4种,因此上面的这些总计是7种
假设现在有5个台阶,那么小孩跳到第五个台阶的方法有13种,先让小孩跳到第二个台阶,再从第二个台阶直接到第五个台阶…
因此规律就找到了,其实就是一个斐波那契数列的变形问题,利用上面的例题的思路就可以解决这个问题
class Solution
{
public:int waysToStep(int n) {vector<long long> dp(n+4);dp[0]=0;dp[1]=1;dp[2]=2;dp[3]=4;for(int i=4;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];dp[i] %= 1000000007;}return dp[n];}
};
使用最小花费爬楼梯
此题也是动态规划中的一个典型题,这里从两个角度来看这道题
从最开始的介绍中可以知道,对于动态规划的问题来说,关键是dp[i]
的意义和状态转移方程,在解决问题的过程中要优先对这两个部分进行思考和解决,那么两个不同的dp[i]
的角度来看这个题
首先从第一个角度来看:
如果这里的dp[i]
表示的是,上到第i个台阶需要花费多少钱:
那么可以这样思考问题,要知道上到第i个台阶需要多少钱,就必然要知道上到第i-1个台阶要花多少钱,再用这个钱加上上第i-1个台阶要花多少钱,由于一次可以上两个台阶,因此也要知道上到第i-2个台阶需要多少钱和上这个台阶需要多少钱,再比较一下从第i-1个台阶上划算还是从第i-2个台阶上划算,比较后就可以得到dp[i]
的值,因此状态转移方程就很容易得到了
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
此时注意一下边界初始化问题:在第0和第1个台阶是不需要花钱的,于是初始化为0即可,代码也可以很好的实现出来
class Solution
{
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+1);dp[0]=0;dp[1]=0;for(int i=2;i<=cost.size();i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.size()];}
};
以上为第一种思考的方式,dp[i]
对应的意义还有其他,这里还可以理解为从第i个位置上到最顶上需要的花费,因此这里也可以借助这个意义来解决
那如果要求从第i个台阶上到顶端要花多少钱,需要知道从第i个台阶一次上一个台阶还是一次上两个台阶比较划算,因此这里又需要知道i+1和i+2的值,根据这两个的值决定一次上一个台阶还是上两个台阶,因此状态转移方程也可以得出来了:
dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
那么代码的实现也可以得出:
class Solution
{
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int> dp(n);dp[n-1]=cost[n-1];dp[n-2]=cost[n-2];for(int i=n-3;i>=0;i--){dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);}return min(dp[0],dp[1]);}
};
相关文章:

算法:动态规划的入门理解
文章目录 算法原理题目解析第n个泰波那契数列三步问题使用最小花费爬楼梯 从本篇开始总结的是动态规划的一些内容,动态规划是算法中非常重要的一个版块,因此也是学习算法中的一个重点,在学习动态规划前应当要把动态规划的基础知识学习一下 算…...

最新版nacos 2.2.3服务注册与发现版本依赖问题
最新版nacos的注册服务时配置文件写的是对的,但就是在nacos web页面无法看见服务,此时你需要注意你的依赖是否正确 spring: application:name: orderservicecloud:nacos:discovery:server-addr: 122.51.115.127:8848父工程依赖:现在最新的s…...

2023年中国合同能源管理行业研究报告
第一章 行业概况 1.1 定义及分类 合同能源管理 (Energy Performance Contracting, EPC) 是当前能源行业中一个重要的概念,它构建了一个桥梁,将节能服务公司 (Energy Management Company, EMCo) 与用能单位紧密联系在一起。通过特定的契约形式ÿ…...

php以半小时为单位,输出指定的时间范围
//可预订小时范围$hour [];for ($i$startHour*3600;$i<$endHour*3600;$i1800){//以半小时为单位输出$startHourItem date(H:i,strtotime(date(Y-m-d))$i);//小时开始$endHourItem date(H:i,strtotime(date(Y-m-d))$i1800);//当前时间再加半小时$hourItemStr $startHourI…...
Electron应用的 asar 打包 解压
前言: .asar文件是一种归档文件格式,通常用于封装Electron应用程序的资源。Electron是一个使得开发者能够使用Web技术构建跨平台桌面应用程序的框架。为了提高性能和简化部署,Electron应用程序的资源通常会被打包到一个.asar文件中。 安装 as…...
蓝桥等考Python组别十七级003
第一部分:选择题 1、Python L17 (15分) 运行下面程序,输出的结果是( )。 def func(x, y): return (x + y) // 3 print(func(7, 5)) 2468正确答案:B 2、Python L17 (15</...
Redis概述和与SpringBoot的整合
Redis是一种高性能的键值对存储数据库,它支持多种数据结构,包括字符串、哈希、列表、集合和有序集合等。Redis具有快速、可靠、灵活和可扩展等特点,也被广泛应用于缓存、队列和排行榜等场景。 SpringBoot是一种基于Spring框架的快速开发脚手…...
Python 中的 round() 函数:实现精确的数值舍入操作
round(x, n) 函数用于对数值 x 进行舍入操作,并指定保留的小数位数为 n。它的工作原理如下: 如果 x 的小数位数小于等于 n,则直接返回 x 本身。例如,round(3.1415, 2) 将返回 3.14。 如果 x 的小数位数大于 n,则按照四…...
在springboot中如何开启Bean数据校验
①:添加JSR303规范坐标与Hibernate校验框架对应坐标 <dependency><groupId>javax.validation</groupId><artifactId>validation-api</artifactId> </dependency><dependency><groupId>org.hibernate.validator<…...
【C语言好题系列三】
文章目录 学习导航一. 选择题二. 编程题(力扣/牛客网)三. 总结 学习导航 一. 选择题 如下程序的运行结果是(D) char c[5]{a, b, \0, c, \0}; printf("%s", c);A: ‘a’ ‘b’ B: ab\0c\0 C: ab c D: ab 答案解析: 正…...
ElasticSearch搜索引擎:常用的存储mapping配置项 与 doc_values详细介绍
一、ES的数据存储结构: ES底层使用 Lucene 存储数据,Lucene 的索引包含以下部分: A Lucene index is made of several components: an inverted index, a bkd tree, a column store (doc values), a document store (stored fields) and te…...
[Spring]事务的传播机制
一、背景 Mysql在修改完数据后,默认会自动触发事务Commit提交。 而在我们服务的一个方法里,需要多次修改Mysql记录。 为了保证原子性,我们需要将Mysql设为手动提交,多次修改后再commit提交。 二、Spring事务 1、编程式事务管理…...
linux下,如何查看一个文件的哈希值md5以及sha264
在linux终端中,可能存在多个相似的文件,而哈希值可以唯一确定一个文件。文件的哈希值计算可以有以下两种方式,MD5和SHA256,现将两种方式罗列如下: 1、MD5 命令:$ md5sum FileName 一个文件的 MD5 是固定的…...

Java类加载过程
一、前言 我们都知道计算机的底层逻辑都是0和1的编码,当然除了现在所研究的量子计算除外。那么我们在计算机所做的一切操作,底层原理是不是都可以翻译到0和1呢。如果刨根问底的话,可以这么说,当然0和1的表示也属于逻辑门电路电的…...

人脸活体检测技术的应用,有效避免人脸识别容易被攻击的缺陷
随着软件算法和物理终端的进步,人脸识别现在越来越被广泛运用到生活的方方面面,已经成为了重要的身份验证手段,但同时也存在着自身的缺陷,目前常规人脸识别技术可以精准识别目标人像特征,并迅速返回比对结果࿰…...
大数据发展史
一、hadoop发展史 hadoop创始人Doug Cutting,主要为了实现Google类似全文搜索功能,该功能是基于Lucene框架进行优化升级,索引引擎; 2001年底Lucence成为Apache基金会的一个子项目,当时为了解决存储海量数据困难,检索海量速度慢,可以说Google是hadoop的思想之源; GFS…...

有关范数的学习笔记
向量的【范数】:模长的推广,柯西不等式_哔哩哔哩_bilibili 模长 范数 这里UP主给了说明 点赞 范数理解(0范数,1范数,2范数)_一阶范数-CSDN博客 出租车/曼哈顿范数 det()行列式 正定矩阵(Posit…...

如何通过MES系统提高生产计划效率?
导 读 ( 文/ 1730 ) 在现代制造业中,通过制造执行系统(MES)系统来提高生产计划效率是至关重要的。本文将介绍如何通过MES系统来优化生产计划,包括实时数据分析、智能排程和协同协作。通过这些关键方法,企业可以提高生产…...

持续提升信息安全运维保障服务能力,天玑科技助力企业快速实现数字化转型
近年来,以互联网、云计算、大数据、物联网为代表的新一代信息技术快速发展。给人们的生产生活方式带来方便的同时,也给信息系统的安全带来了严峻的挑战。我国信息化和信息安全保障工作的不断深入推进,以应急处理、风险评估、灾难恢复、系统测…...

【PostgreSQL启动,停止命令(重启)】
找到 /usr/lib/systemd/system文件夹路径看是否包含 postgresql服务 关闭服务: systemctl stop postgresql-12.service启动服务 systemctl start postgresql-12.service重启服务 systemctl restart postgresql-12查看状态 systemctl status postgresql-12.servi…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
智能职业发展系统:AI驱动的职业规划平台技术解析
智能职业发展系统:AI驱动的职业规划平台技术解析 引言:数字时代的职业革命 在当今瞬息万变的就业市场中,传统的职业规划方法已无法满足个人和企业的需求。据统计,全球每年有超过2亿人面临职业转型困境,而企业也因此遭…...

Xcode 16 集成 cocoapods 报错
基于 Xcode 16 新建工程项目,集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

华为云Flexus+DeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手
华为云FlexusDeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手 一、构建知识库问答助手引言二、构建知识库问答助手环境2.1 基于FlexusX实例的Dify平台2.2 基于MaaS的模型API商用服务 三、构建知识库问答助手实战3.1 配置Dify环境3.2 创建知识库问答助手3.3 使用知…...
民锋视角下的资金流效率与账户行为建模
民锋视角下的资金流效率与账户行为建模 在当前复杂多变的金融环境中,资金流效率已成为衡量一家金融服务机构专业能力的重要指标。民锋在账户管理与资金调配的实战经验中,逐步建立起一套以资金流路径为核心的行为建模方法,用以评估客户行为、交…...