动态规划学习总结 dynamic programming

2024-06-20 07:08

本文主要是介绍动态规划学习总结 dynamic programming,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

因为阅读论文的原因,看到有dynamic programming 就学习一下,在知乎上,看到回答解释帖子:

作者:徐凯强 Andy
链接:https://www.zhihu.com/question/23995189/answer/35324479
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

我曾经作为省队成员参加过NOI,保送之后也给学校参加NOIP的同学多次讲过动态规划,我试着讲一下我理解的动态规划,争取深入浅出。希望你看了我的答案,能够喜欢上动态规划。

0. 动态规划的本质,是对问题 状态的定义状态转移方程的定义
引自维基百科
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
本题下的其他答案,大多都是在说递推的求解方法,但如何拆分问题,才是动态规划的核心。
拆分问题,靠的就是状态的定义状态转移方程的定义

1. 什么是 状态的定义?

首先想说大家千万不要被下面的数学式吓到,这里只涉及到了函数相关的知识。

我们先来看一个动态规划的教学必备题:
给定一个数列,长度为N,
求这个数列的最长上升(递增)子数列(LIS)的长度.

1 7 2 8 3 4
为例。
这个数列的最长递增子数列是 1 2 3 4,长度为4;
次长的长度为3, 包括 1 7 8; 1 2 3 等.

要解决这个问题,我们首先要定义这个问题和这个问题的子问题。
有人可能会问了,题目都已经在这了,我们还需定义这个问题吗?需要,原因就是这个问题在字面上看,找不出子问题,而没有子问题,这个题目就没办法解决。

所以我们来重新定义这个问题:
给定一个数列,长度为N,
F_{k}为:以数列中第k项结尾的最长递增子序列的长度.
F_{1}..F_{N} 中的最大值.

显然,这个新问题与原问题等价。
而对于F_{k}来讲,F_{1} .. F_{k-1}都是F_{k}的子问题:因为以第k项结尾的最长递增子序列(下称LIS),包含着以第1..k-1中某项结尾的LIS。

上述的新问题F_{k}也可以叫做状态,定义中的“F_{k}为数列中第k项结尾的LIS的长度”,就叫做对状态的定义。
之所以把F_{k}做“状态”而不是“问题” ,一是因为避免跟原问题中“问题”混淆,二是因为这个新问题是数学化定义的。


对状态的定义只有一种吗? 当然不是
我们甚至可以二维的,以完全不同的视角定义这个问题:
给定一个数列,长度为N,
F_{i, k}为:
在前i项中的,长度为k的最长递增子序列中,最后一位的最小值. 1\leq k\leq N.
若在前i项中,不存在长度为k的最长递增子序列,则 F_{i, k}为正无穷.
求最大的x,使得 F_{N,x}不为正无穷。

这个新定义与原问题的等价性也不难证明,请读者体会一下。
上述的F_{i, k}就是状态,定义中的“F_{i, k}为:在前i项中,长度为k的最长递增子序列中,最后一位的最小值”就是对状态的定义。


2. 什么是状态转移方程
上述状态定义好之后,状态和状态之间的关系式,就叫做状态转移方程。

比如,对于LIS问题,我们的第一种定义:
F_{k}为:以数列中第k项结尾的最长递增子序列的长度.
设A为题中数列,状态转移方程为:
F_{1} = 1 (根据状态定义导出边界情况)
F_{k}=max(F_{i}+1 | A_{k}>A_{i}, i\in (1..k-1)) (k>1)

用文字解释一下是:
以第k项结尾的LIS的长度是:保证第i项比第k项小的情况下,以第i项结尾的LIS长度加一的最大值,取遍i的所有值(i小于k)。

第二种定义:
F_{i, k}为:在数列前i项中,长度为k的递增子序列中,最后一位的最小值
设A为题中数列,状态转移方程为:
A_{i}>F_{i-1,k-1}F_{i,k}=min(A_{i},F_{i-1,k})
否则: F_{i,k}=F_{i-1,k}

(边界情况需要分类讨论较多,在此不列出,需要根据状态定义导出边界情况。)
大家套着定义读一下公式就可以了,应该不难理解,就是有点绕。

这里可以看出,这里的状态转移方程,就是定义了问题和子问题之间的关系。
可以看出,状态转移方程就是带有条件的递推式。

3. 动态规划迷思
本题下其他用户的回答跟动态规划都有或多或少的联系,我也讲一下与本答案的联系。

a. “缓存”,“重叠子问题”,“记忆化”:
这三个名词,都是在阐述递推式求解的技巧。以Fibonacci数列为例,计算第100项的时候,需要计算第99项和98项;在计算第101项的时候,需要第100项和第99项,这时候你还需要重新计算第99项吗?不需要,你只需要在第一次计算的时候把它记下来就可以了。
上述的需要再次计算的“第99项”,就叫“重叠子问题”。如果没有计算过,就按照递推式计算,如果计算过,直接使用,就像“缓存”一样,这种方法,叫做“记忆化”,这是递推式求解的技巧。这种技巧,通俗的说叫“花费空间来节省时间”。都不是动态规划的本质,不是动态规划的核心。

b. “递归”:
递归是递推式求解的方法,连技巧都算不上。

c. "无后效性",“最优子结构”:
上述的状态转移方程中,等式右边不会用到下标大于左边i或者k的值,这是"无后效性"的通俗上的数学定义,符合这种定义的状态定义,我们可以说它具有“最优子结构”的性质,在动态规划中我们要做的,就是找到这种“最优子结构”。
在对状态和状态转移方程的定义过程中,满足“最优子结构”是一个隐含的条件(否则根本定义不出来)。对状态和“最优子结构”的关系的进一步解释,什么是动态规划?动态规划的意义是什么? - 王勐的回答 写的很好,大家可以去读一下。

需要注意的是,一个问题可能有多种不同的状态定义和状态转移方程定义,存在一个有后效性的定义,不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区:
动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义在找到之后,这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义,才是动态规划的本质。

有位答主说:
分治在求解每个子问题的时候,都要进行一遍计算
动态规划则存储了子问题的结果,查表时间为常数

这就像说多加辣椒的菜就叫川菜,多加酱油的菜就叫鲁菜一样,是存在误解的。

文艺的说,动态规划是寻找一种对问题的观察角度,让问题能够以递推(或者说分治)的方式去解决。寻找看问题的角度,才是动态规划中最耀眼的宝石!(大雾)
-------

另外一部分,讲述的比较清楚:

作者:王勐
链接:https://www.zhihu.com/question/23995189/answer/35429905
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

动态规划的本质不在于是递推或是递归,也不需要纠结是不是内存换时间。

理解动态规划并不需要数学公式介入,只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是动态规划可以解决的,才能明白为神马需要动态规划。不过好处时顺便也就搞明白了递推贪心搜索和动规之间有什么关系,以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然熟悉了之后可以直接根据问题的描述得到思路,如果有需要的话再补充吧。

动态规划是对于 某一类问题 的解决方法!!重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推!

怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机,内存里存储的所有数据构成了当前的状态,CPU只能利用当前的状态计算出下一个状态(不要纠结硬盘之类的外部存储,就算考虑他们也只是扩大了状态的存储容量而已,并不能改变下一个状态只能从当前状态计算出来这一条铁律)


当你企图使用计算机解决一个问题是,其实就是在思考如何将这个问题表达成状态(用哪些变量存储哪些数据)以及如何在状态中转移(怎样根据一些变量计算出另一些变量)。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少,所谓时间复杂度就是从初始状态到达最终状态中间需要多少步!

太抽象了还是举个例子吧:

比如说我想计算第100个非波那契数,每一个非波那契数就是这个问题的一个状态,每求一个新数字只需要之前的两个状态。所以同一个时刻,最多只需要保存两个状态,空间复杂度就是常数;每计算一个新状态所需要的时间也是常数且状态是线性递增的,所以时间复杂度也是线性的。

上面这种状态计算很直接,只需要依照固定的模式从旧状态计算出新状态就行(a[i]=a[i-1]+a[i-2]),不需要考虑是不是需要更多的状态,也不需要选择哪些旧状态来计算新状态。对于这样的解法,我们叫递推。

非波那契那个例子过于简单,以至于让人忽视了阶段的概念,所谓阶段是指随着问题的解决,在同一个时刻可能会得到的不同状态的集合。非波那契数列中,每一步会计算得到一个新数字,所以每个阶段只有一个状态。想象另外一个问题情景,假如把你放在一个围棋棋盘上的某一点,你每一步只能走一格,因为你可以东南西北随便走,所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段,走了n步可能处于的位置称为一个状态,走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。

现在问题来了,有了阶段之后,计算新状态可能会遇到各种奇葩的情况,针对不同的情况,就需要不同的算法,下面就分情况来说明一下:


假如问题有n个阶段,每个阶段都有多个状态,不同阶段的状态数不必相同,一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。

好消息是,有时候我们并不需要真的计算所有状态,比如这样一个弱智的棋盘问题:从棋盘的左上角到达右下角最短需要几步。答案很显然,用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态,正如这个问题中走n步可以走到很多位置一样。但是同样n步中,有哪些位置可以让我们在第n+1步中走的最远呢?没错,正是第n步中走的最远的位置。换成一句熟悉话叫做“下一步最优是从当前最优得到的”。所以为了计算最终的最优值,只需要存储每一步的最优值即可,解决符合这种性质的问题的算法就叫贪心。如果只看最优状态之间的计算过程是不是和非波那契数列的计算很像?所以计算的方法是递推。

既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题:一个阶段的最优可以由前一个阶段的最优得到。

如果一个阶段的最优无法用前一个阶段的最优得到呢?

什么你说只需要之前两个阶段就可以得到当前最优?那跟只用之前一个阶段并没有本质区别。最麻烦的情况在于你需要之前所有的情况才行。

再来一个迷宫的例子。在计算从起点到终点的最短路线时,你不能只保存当前阶段的状态,因为题目要求你最短,所以你必须知道之前走过的所有位置。因为即便你当前再的位置不变,之前的路线不同会影响你的之后走的路线。这时你需要保存的是之前每个阶段所经历的那个状态,根据这些信息才能计算出下一个状态!

每个阶段的状态或许不多,但是每个状态都可以转移到下一阶段的多个状态,所以解的复杂度就是指数的,因此时间复杂度也是指数的。哦哦,刚刚提到的之前的路线会影响到下一步的选择,这个令人不开心的情况就叫做有后效性。

刚刚的情况实在太普遍,解决方法实在太暴力,有没有哪些情况可以避免如此的暴力呢?

契机就在于后效性。

有一类问题,看似需要之前所有的状态,其实不用。不妨也是拿最长上升子序列的例子来说明为什么他不必需要暴力搜索,进而引出动态规划的思路。

假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢?需要从头到尾依次枚举是否选择当前的数字,每选定一个数字就要去看看是不是满足“上升”的性质,这里第i个阶段就是去思考是否要选择第i个数,第i个阶段有两个状态,分别是选和不选。哈哈,依稀出现了刚刚迷宫找路的影子!咦慢着,每次当我决定要选择当前数字的时候,只需要和之前选定的一个数字比较就行了!这是和之前迷宫问题的本质不同!这就可以纵容我们不需要记录之前所有的状态啊!既然我们的选择已经不受之前状态的组合的影响了,那时间复杂度自然也不是指数的了啊!虽然我们不在乎某序列之前都是什么元素,但我们还是需要这个序列的长度的。所以我们只需要记录以某个元素结尾的LIS长度就好!因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的,然后就得到了DP方程(感谢

@河谐
指正)
LIS(i)=max\{LIS(j)+1\} \ \ \ \ j<i \ and\ a[j] < a[i]

所以一个问题是该用递推、贪心、搜索还是动态规划,完全是由这个问题本身阶段间状态的转移方式决定的!

每个阶段只有一个状态->递推;
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心;
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索;
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到

这个性质叫做最优子结构;

而不管之前这个状态是如何得到的

这个性质叫做无后效性。

另:其实动态规划中的最优状态的说法容易产生误导,以为只需要计算最优状态就好,LIS问题确实如此,转移时只用到了每个阶段“选”的状态。但实际上有的问题往往需要对每个阶段的所有状态都算出一个最优值,然后根据这些最优值再来找最优状态。比如背包问题就需要对前i个包(阶段)容量为j时(状态)计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。

reference link:  https://www.zhihu.com/question/23995189


----自己总结:

1. 在一定限定条件下,定义我求解问题的状态,所包含的东西,但是,描述这个状态的转移方程以递推关系,进行展开,并且,在对应的求解中,会利用不断的递推关系,来进一步逼近我们所遇到的问题的解,拆分问题(本质是利用状态转移空间,对相关的空间状态进行对应的描述,然后利用对应的),而在后面的求解方程限制的时候,会出现无后效性的观点,描述的是,f,k=f(f,k-1)坐标之间存在坐标大小不大于的关系,但是,和这个状态如何获得,没有相关的关系,而满足这种性质的情况,称为“最优子结构”,递归,分开,但是,和之前的分治算法,有所不同,注意体会。

2. 第二个解释的时候,融合进了状态机模型,并且把时间复杂度,空间复杂度融合进去了,耳目一新的理解(当然,对于科班出生,这些是基本理解),但是,自己要不断地联想,之前状态机,和时间/空间复杂度都学习了,但是,如何融合在一起,就需要想想,如何实现知识的融会贯通。

3.对于dynamic programming的理解,还是有比较浅显,在阅读完yuZheng的论文之后,再重读,更新下,对应的理解部分,夯实基础。[20170104]

这篇关于动态规划学习总结 dynamic programming的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1077436

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的