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

算法:动态规划的入门理解

文章目录

  • 算法原理
  • 题目解析
    • 第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个泰波那契数列三步问题使用最小花费爬楼梯 从本篇开始总结的是动态规划的一些内容&#xff0c;动态规划是算法中非常重要的一个版块&#xff0c;因此也是学习算法中的一个重点&#xff0c;在学习动态规划前应当要把动态规划的基础知识学习一下 算…...

最新版nacos 2.2.3服务注册与发现版本依赖问题

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

2023年中国合同能源管理行业研究报告

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

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 打包 解压

前言&#xff1a; .asar文件是一种归档文件格式&#xff0c;通常用于封装Electron应用程序的资源。Electron是一个使得开发者能够使用Web技术构建跨平台桌面应用程序的框架。为了提高性能和简化部署&#xff0c;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是一种高性能的键值对存储数据库&#xff0c;它支持多种数据结构&#xff0c;包括字符串、哈希、列表、集合和有序集合等。Redis具有快速、可靠、灵活和可扩展等特点&#xff0c;也被广泛应用于缓存、队列和排行榜等场景。 SpringBoot是一种基于Spring框架的快速开发脚手…...

Python 中的 round() 函数:实现精确的数值舍入操作

round(x, n) 函数用于对数值 x 进行舍入操作&#xff0c;并指定保留的小数位数为 n。它的工作原理如下&#xff1a; 如果 x 的小数位数小于等于 n&#xff0c;则直接返回 x 本身。例如&#xff0c;round(3.1415, 2) 将返回 3.14。 如果 x 的小数位数大于 n&#xff0c;则按照四…...

在springboot中如何开启Bean数据校验

①&#xff1a;添加JSR303规范坐标与Hibernate校验框架对应坐标 <dependency><groupId>javax.validation</groupId><artifactId>validation-api</artifactId> </dependency><dependency><groupId>org.hibernate.validator<…...

【C语言好题系列三】

文章目录 学习导航一. 选择题二. 编程题(力扣/牛客网&#xff09;三. 总结 学习导航 一. 选择题 如下程序的运行结果是&#xff08;D&#xff09; char c[5]{a, b, \0, c, \0}; printf("%s", c);A: ‘a’ ‘b’ B: ab\0c\0 C: ab c D: ab 答案解析&#xff1a; 正…...

ElasticSearch搜索引擎:常用的存储mapping配置项 与 doc_values详细介绍

一、ES的数据存储结构&#xff1a; ES底层使用 Lucene 存储数据&#xff0c;Lucene 的索引包含以下部分&#xff1a; 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在修改完数据后&#xff0c;默认会自动触发事务Commit提交。 而在我们服务的一个方法里&#xff0c;需要多次修改Mysql记录。 为了保证原子性&#xff0c;我们需要将Mysql设为手动提交&#xff0c;多次修改后再commit提交。 二、Spring事务 1、编程式事务管理…...

linux下,如何查看一个文件的哈希值md5以及sha264

在linux终端中&#xff0c;可能存在多个相似的文件&#xff0c;而哈希值可以唯一确定一个文件。文件的哈希值计算可以有以下两种方式&#xff0c;MD5和SHA256&#xff0c;现将两种方式罗列如下&#xff1a; 1、MD5 命令&#xff1a;$ md5sum FileName 一个文件的 MD5 是固定的…...

Java类加载过程

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

人脸活体检测技术的应用,有效避免人脸识别容易被攻击的缺陷

随着软件算法和物理终端的进步&#xff0c;人脸识别现在越来越被广泛运用到生活的方方面面&#xff0c;已经成为了重要的身份验证手段&#xff0c;但同时也存在着自身的缺陷&#xff0c;目前常规人脸识别技术可以精准识别目标人像特征&#xff0c;并迅速返回比对结果&#xff0…...

大数据发展史

一、hadoop发展史 hadoop创始人Doug Cutting&#xff0c;主要为了实现Google类似全文搜索功能,该功能是基于Lucene框架进行优化升级,索引引擎; 2001年底Lucence成为Apache基金会的一个子项目,当时为了解决存储海量数据困难,检索海量速度慢,可以说Google是hadoop的思想之源; GFS…...

有关范数的学习笔记

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

如何通过MES系统提高生产计划效率?

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

持续提升信息安全运维保障服务能力,天玑科技助力企业快速实现数字化转型

近年来&#xff0c;以互联网、云计算、大数据、物联网为代表的新一代信息技术快速发展。给人们的生产生活方式带来方便的同时&#xff0c;也给信息系统的安全带来了严峻的挑战。我国信息化和信息安全保障工作的不断深入推进&#xff0c;以应急处理、风险评估、灾难恢复、系统测…...

【PostgreSQL启动,停止命令(重启)】

找到 /usr/lib/systemd/system文件夹路径看是否包含 postgresql服务 关闭服务&#xff1a; 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…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 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驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 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 使用知…...

民锋视角下的资金流效率与账户行为建模

民锋视角下的资金流效率与账户行为建模 在当前复杂多变的金融环境中&#xff0c;资金流效率已成为衡量一家金融服务机构专业能力的重要指标。民锋在账户管理与资金调配的实战经验中&#xff0c;逐步建立起一套以资金流路径为核心的行为建模方法&#xff0c;用以评估客户行为、交…...