基础dp——动态规划

目录

一、什么是动态规划？

二、动态规划的使用步骤

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

三、试题讲解

1.最小花费爬楼梯

2.下降路径最小和

3.解码方法

一、什么是动态规划？

        动态规划（Dynamic Programming，简称dp）是一种通过将复杂问题分解为更小的子问题来解决的算法思想，尤其适用于具有重叠子问题和最优子结构的优化问题。其核心目标是避免重复计算，通过存储中间结果（记忆化）来提升效率。

动态规划 vs 分治法

  • 共同点：都将问题分解为子问题。

  • 区别：

    • 分治法（如归并排序）的子问题独立，无重叠，无需存储中间结果。

    • 动态规划的子问题有重叠，需存储中间结果避免重复计算。

二、动态规划的使用步骤

        为了方便理解下面我将从感性的角度来给大家讲解动态规划的使用步骤

1.状态表示

        首先在解决问题的时候我们通常会使用一块空间来记录已处理的数据，我们把这块空间叫作dp表。

        当我们在解决一个小问题时需要借助之前已解决的问题的数据，就可以到dp表里面查，当前这个小问题解决后继续把它相关的信息存到dp表，然后继续解决下一个小问题。

        这个dp表中的一小块数据表示什么？这些问题指的就是状态表示。在用动态规划解决问题时，要面对最重要的问题就是dp表的状态应该表示是什么？

在解决这个问题时我们通常都是从这几个角度去思考：

  • 1.经验+题目要求
  • 2.分析问题的过程中，发现重复子问题。
  • 3.当我们发现子问题后，假设前（或后）几个小问题已经解决，思考我们在解决当前问题时有没有需要前面已解决的问题的什么信息？

2.状态转移方程

        dp[i]等于什么？这就是状态转移方程。它通常要依赖于已经计算过的状态。

3.初始化

在创建好dp表后主要任务就是对dp表的填写，初始化dp表的作用有以下两点：

  1. 保证填表的时候不越界。
  2. 保证填表的正确性。

4.填表顺序

        为使填写当前状态的时候，所需要的状态已经计算过了。

5.返回值

        最后结合题目要求和状态表示计算结果并返回。

三、试题讲解

1.最小花费爬楼梯

        首先我们分析题目，我们的起点是0或1的位置，而终点是n位置（注意不是n-1位置）。我们在爬楼梯时支付一次费用可以爬一个或两个台阶。

        当我们尝试从动态规划方向去解决，那么我们试着去构造一下相同的子问题，并且假设它已经解决。

注：为了方便在下文我都会把动态规划简称为“动规” 

        用动规解题过程中，在找子问题时我总结了一个很厉害的小技巧，就是保留主问题的逻辑，而换一个问题的对象。比如这里，主问题是从起点爬到楼顶的最小花费，那么构造子问题时我们只需要保留这个问题的逻辑，而把楼顶这个对象改成任意位置i。那么我们就得到了一个子问题（即从起点爬到i位置的最小花费）。然后我们再假设前面的相同的子问题已经解决。

比如：

        动规题复杂多变，以上技巧可以解决大部分的基础动规题，但更多的只是作为一个小经验，并不是所有动规题都可以通过构建子问题来解决的。

        在解一个题时，状态表示可以是很多，不同的状态表示就决定了不同的状态转移方程，而要判断一个状态表示是否正确只需看是否能根据该状态表示推出正确的状态转移方程。

能够理解上图那么动态规划的五步骤就水到渠成了。

  • 状态表示： dp[i]：表示爬到i时的最小花费
  • 状态转移方程： dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
  • 初始化： dp表初始化为全0
  • 填表顺序： 从下标为2的位置开始，并且从左往右填写
  • 返回值： return dp[n]

代码示例：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost){int n=cost.size();vector<int> dp(n+1);//默认值就是0，不用初始化for(int i=2;i<=n;i++) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);return dp[n];    }
};

        除了刚才的状态表示我们还可以换一个，只需要改变一下子问题，同样的技巧，主问题逻辑不变，把起点这个对象改成任意位置i， 那么我们就得到了一个子问题（即从i位置爬到楼顶的最小花费）。

  • 状态表示： dp[i]：表示从i爬到楼顶的最小花费
  • 状态转移方程： dp[i]=cost[i]+min(dp[i+1],dp[i+2])
  • 初始化： dp[n-1]=cost[n-1]，dp[n-2]=cost[n-2]
  • 填表顺序： 从右往左
  • 返回值： return min(dp[0], dp[1])

        我们可以发现状态表示的改变使得其他四个步骤的实现逻辑改变，所以可见状态表示的重要性。

代码示例：

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]=cost[i]+min(dp[i+1],dp[i+2]);return min(dp[0],dp[1]);    }
};

        提示：空间优化：在我们填写某一个状态的时候只需要使用它的前两个状态，所以可以把dp数组简化为两个变量就可以解决问题（需要注意变量的更新）。通常把该优化方法叫做“滚动数组”。很多基础动规都可以进行这样的优化，大家可以试着去实现，这一点在后面也不再提。 

        提示：为了减少逻辑上的赘述，在以下题解中我都只会讲解一种状态表示作为示例。 

2.下降路径最小和

通过上一题找子问题的经验，我们可以这样做：

抓住主问题：从第一行任意位置下降到最后一行的任意一个位置的最小和。 

        保留问题的主逻辑，把对象“第一行任意位置”或“最后一行任意位置”更改，比如更改“最后一行任意位置”为“第i行的任意位置j”。得到子问题，即从“第一行任意位置下降到第i行的任意位置j的最小和”。

        接下来假设与它相同的子问题都解决，并利用它们的结果。如下：

动规五步骤：

  • 状态表示： dp[i][j]：从第一行任意位置下降到第i行j列的最小和
  • 状态转移方程： dp[i][j]=matrix[i][j]+min(dp[i-1][j-1]，min(dp[i-1][j]，dp[i-1][j+1]) )
  • 初始化：越界区域如下：

        

        创建(n+1)*(n+2)的dp表初始化为全INT_MAX（这样创建dp表减少了为防止越界而做特殊判断带来的成本）,再将第一行初始化为全0。把dp表初始化为全INT_MAX，是为了防止越界区域参与最小值的筛选。再把第一行初始化为全0是逻辑需要，总的目的都是为了保证填表的正确性。

  • 填表顺序： 从上到下，从左往右（或从右往左，只要能保证在填写当前状态时需要的状态已计算过即可）
  • 返回值： 返回最后一行的最小值

代码示例： 

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix){int n=matrix.size();//题目明确指出是方形，所以行数和列数都一样。vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));for(int j=0;j<n+2;j++) dp[0][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=matrix[i-1][j-1]+min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]);int ret=INT_MAX;for(int j=1;j<=n;j++) ret=min(ret,dp[n][j]);return ret;}
};

3.解码方法

        主问题： 一个非空字符s的解码方法的总数。但我们好像无法从中获取到可以更改的对象，再回去观察上面我们解决的两道问题。它们主问题的逻辑中都是带有区间式的，比如第一题：从起点到终点，第二题：从第一行到最后一行。那么如果我们还想要那个找子问题的技巧去确定状态表示，那么在总结主问题时就要朝着带有区间式的方向去想。

        这里我们可以把主问题总结为：从s字符串的下标0开始到下标n-1结束的解码方法总数。那么这样我们就构造出了一个区间“开始”——“结束”。子问题就好构建得多了。

子问题：从下标0开始到下标i结束的解码方法总数。

  • 状态表示： dp[i]：表示从下标0开始到下标i结束的解码方法总数
  • 状态转移方程：

        解决了状态表示但这个题的难点主要在于状态转移方程。

     

         我们可以把单独解码与和前一个联合解码分开讨论。如果单独解码成功相当于在i-1的所有解码方法中统一加上一个s[i]，所以为dp[i-1]，解码失败的话，说明不能单独解码，所以结果为0。

        同理联合解码成功相当于在i-2的所有解码方法中统一加上一个s[i]与s[i-1]的复合，所以为dp[i-2]，解码失败的话，说明不能联合解码所以结果为0。最后只需要把单独解码与联合解码的结果相加。

  • 初始化： 因为我们在用dp[i]时需要用到dp[i-1]和dp[i-2]的状态，所以最好把dp[0]和dp[1]初始化。dp[0]可以这样写dp[0]=s[i]!='0'，但dp[1]的初始化会比较麻烦，它的初始化逻辑和上面的状态转移方程是一样的。而在下面填表时同样要用到这样的逻辑，就会显得很累赘。

        我们可以使用这样一个初始化技巧：

        那么可以做一个n+1大小的dp表，然后错开一位表示，即 dp[i]：表示从下标0开始到下标i-1结束的解码方法总数。为保证后面的填表顺序正确我们需要dp[1]=s[i]!='0'，这是必然的。而dp[0]该初始化为什么？我们可以思考什么时候用到dp[0]，即s[0]与s[1]解码成功时，那么它必然是dp[0]=1

  • 填表顺序：从dp的2下标开始，并从左往右。
  • 返回值： return dp[n]

代码示例：

class Solution {
public:int numDecodings(string s){vector<int> dp(s.size()+1,0);dp[1]=s[0]!='0',dp[0]=1;for(int i=2;i<dp.size();i++){int m=(s[i-2]-'0')*10+s[i-1]-'0';if(s[i-1]!='0') dp[i]+=dp[i-1];if(m>=10&&m<=26) dp[i]+=dp[i-2];}return dp.back();}
};

非常感谢您能耐心读完这篇文章。倘若您从中有所收获，还望多多支持呀！74c0781738354c71be3d62e05688fecc.png

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Java+Vue+SpringBoot+数据可视化的小吃摊位管理平台(程序+论文+讲解+安装+调试+售后）

Java+Vue+SpringBoot+数据可视化的小吃摊位管理平台(程序+论文+讲解+安装+调试+售后）

感兴趣的可以先收藏起来&#xff0c;还有大家在毕设选题&#xff0c;项目以及论文编写等相关问题都可以给我留言咨询&#xff0c;我会一一回复&#xff0c;希望帮助更多的人。 系统介绍 在繁华的美食街区&#xff0c;美食摊位星罗棋布&#xff0c;每天都上演着热闹非凡的烟火…
阅读更多...
链表-基础训练（二）链表 day14

链表-基础训练（二）链表 day14

两两交换链表中的节点 题目示意&#xff1a; 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 原先我的思路是图像上的思路&#xff0c;但是我感觉还是很复杂…
阅读更多...
进程概念、PCB及进程查看

进程概念、PCB及进程查看

文章目录 一.进程的概念进程控制块&#xff08;PCB&#xff09; 二.进程查看通过指令查看进程通过proc目录查看进程的cwd和exe获取进程pid和ppid通过fork()创建子进程 一.进程的概念 进程是一个运行起来的程序&#xff0c;而程序是存放在磁盘的&#xff0c;cpu要想执行程序的指…
阅读更多...
极客大学 java 进阶训练营怎么样，图文详解

极客大学 java 进阶训练营怎么样，图文详解

Spring 思维导图 Spring 源码学习笔记 有关微服务的面试题&#xff1a; Dubbo中zookeeper做注册中心&#xff0c;如果注册中心集群都挂掉&#xff0c;发布者和订阅者之间还能通信么&#xff1f;微服务学习笔记 有关分布式的面试题&#xff1a; 消息幂等:如何保证消息不被重复…
阅读更多...
如何手动设置u-boot的以太网的IP地址、子网掩码、网关信息、TFTP的服务器地址,并进行测试

如何手动设置u-boot的以太网的IP地址、子网掩码、网关信息、TFTP的服务器地址,并进行测试

设置IP地址 运行下面这条命令设置u-boot的以太网的IP地址&#xff1a; setenv ipaddr 192.168.5.9设置子网掩码 运行下面这条命令设置u-boot的以太网的子网掩码&#xff1a; setenv netmask 255.255.255.0设置网关信息 运行下面这条命令设置u-boot的网关信息&#xff1a; …
阅读更多...
使用大语言模型对接OA系统，实现会议室预定功能

使用大语言模型对接OA系统，实现会议室预定功能

随着人工智能技术的不断进步&#xff0c;越来越多的企业开始借助 AI 助手来提高工作效率&#xff0c;尤其是在日常事务的自动化处理中。比如&#xff0c;在许多公司里&#xff0c;会议室的预定是一个常见且频繁的需求&#xff0c;通常需要员工手动检查空闲时间并做出选择。而通…
阅读更多...
单链表：数据结构中的灵活“链条”

单链表：数据结构中的灵活“链条”

目录 &#x1f680;前言&#x1f914;单链表是什么&#xff1f;&#x1f4af;单链表的结构特点&#x1f4af;单链表的用途 ✍️单链表的实现与接口解释&#x1f4af;打印链表&#x1f4af;尾插操作&#x1f4af;头插操作&#x1f4af;头删操作&#x1f4af;尾删操作&#x1f4a…
阅读更多...
Redis面试宝典【刷题系列】

Redis面试宝典【刷题系列】

文章目录 一、什么是Redis&#xff1f;二、Redis相比Memcached有哪些优势&#xff1f;三、Redis支持的数据类型有哪些&#xff1f;四、Redis的主要消耗的物理资源是什么&#xff1f;五、Redis的全称是什么&#xff1f;六、Redis有哪些数据淘汰策略&#xff1f;七、为什么Redis需…
阅读更多...
uni-app集成sqlite

uni-app集成sqlite

Sqlite SQLite 是一种轻量级的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;广泛应用于各种应用程序中&#xff0c;特别是那些需要嵌入式数据库解决方案的场景。它不需要单独的服务器进程或系统配置&#xff0c;所有数据都存储在一个单一的普通磁盘文件中&am…
阅读更多...
pytest-html

pytest-html

首先安装pytest-html库 #执行命令 pytest --htmlreport.html ./pytest-html.pyimport pytest import logging def test_pass():"""用例通过"""assert Truedef test_fail():"""用例失败"""assert Falsedef test_e…
阅读更多...
kafka为什么这么快？

kafka为什么这么快？

前言 Kafka的高效有几个关键点&#xff0c;首先是顺序读写。磁盘的顺序访问速度其实很快&#xff0c;甚至比内存的随机访问还要快。Kafka在设计上利用了这一点&#xff0c;将消息顺序写入日志文件&#xff0c;这样减少了磁盘寻道的时间&#xff0c;提高了吞吐量。与传统数据库的…
阅读更多...
从DeepSeek的爆火来看大模型微调技术的发展方向

从DeepSeek的爆火来看大模型微调技术的发展方向

“深度人工智能”是成都深度智谷科技旗下的人工智能教育机构订阅号&#xff0c;主要分享人工智能的基础知识、技术发展、学习经验等。此外&#xff0c;订阅号还为大家提供了人工智能的培训学习服务和人工智能证书的报考服务&#xff0c;欢迎大家前来咨询&#xff0c;实现自己的…
阅读更多...
Dify使用教程（创建应用）

Dify使用教程（创建应用）

Dify的安装部署我已经写过了&#xff0c;简单的模型配置我也在前面进行了讲解&#xff0c;今天我们主要来讲讲如何使用Dify。 一、创建应用 我们可以通过三种方式在Dify的工作室内创建应用 01 基于应用模板创建&#xff08;新手推荐&#xff09;02 创建一个空白应用03 通过D…
阅读更多...
system verilog的流操作符

system verilog的流操作符

流操作符&#xff0c;有分为操作对象是一整个数组和单独的数据两种&#xff0c;例如bit [7:0] a[4]和bit [31:0] b&#xff0c;前者操作对象是数组&#xff0c;后者是单独一个较大位宽的数。 流操作符有<<和>>&#xff0c;代表从右向左打包和从左向右打包。 打包的…
阅读更多...
项目实战--网页五子棋（匹配模块）(4)

项目实战--网页五子棋（匹配模块）(4)

上期我们完成了游戏大厅的前端部分内容&#xff0c;今天我们实现后端部分内容 1. 维护在线用户 在用户登录成功后&#xff0c;我们可以维护好用户的websocket会话&#xff0c;把用户表示为在线状态&#xff0c;方便获取到用户的websocket会话 package org.ting.j20250110_g…
阅读更多...
hot100_108. 将有序数组转换为二叉搜索树

hot100_108. 将有序数组转换为二叉搜索树

hot100_108. 将有序数组转换为二叉搜索树 思路 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 平衡 二叉搜索树。 示例 1&#xff1a; 输入&#xff1a;nums [-10,-3,0,5,9] 输出&#xff1a;[0,-3,9,-10,null,5] 解释&#…
阅读更多...
Win11更新系统c盘爆满处理

Win11更新系统c盘爆满处理

1.打开磁盘管理 2.右击c盘选择属性&#xff0c;进行磁盘管理&#xff0c;选择详细信息。 3.选择以前安装的文件删除即可释放c盘空间。
阅读更多...
深入理解 JSP 与 Servlet：原理、交互及实战应用

深入理解 JSP 与 Servlet：原理、交互及实战应用

一、引言 在 Java Web 开发领域，JSP（JavaServer Pages）和 Servlet 是两个至关重要的技术，它们共同构成了动态网页开发的基础。Servlet 作为服务器端的 Java 程序，负责处理客户端请求并生成响应；而 JSP 则是一种简化的 Servlet 开发方式，允许开发者在 HTML 页面中嵌入 J…
阅读更多...
[通俗易懂C++]:指针和const

[通俗易懂C++]:指针和const

之前的文章有说过,使用指针我们可以改变指针指向的内容(通过给指针赋一个新的地址)或者改变被保存地址的值(通过给解引用指针赋一个新值): int main() {int x { 5 }; // 创建一个整数变量 x&#xff0c;初始值为 5int* ptr { &x }; // 创建一个指针 ptr&#xff0c;指向 …
阅读更多...
DL/CV领域常见指标术语(FLOPS/mIoU/混淆矩阵/F1-measure)------一篇入门

DL/CV领域常见指标术语(FLOPS/mIoU/混淆矩阵/F1-measure)------一篇入门

1. FLOPS、FLOPs和GFLOPs FLOPS: floating-point operations per second&#xff0c;每秒浮点运算次数&#xff0c;用来衡量硬件性能。 FLOPs&#xff1a;floating point of operations&#xff0c;是浮点运算次数&#xff0c;用来衡量算法、模型的复杂度。 GFLOPS&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023