动态规划小结

一个入门级见解和总结

动态规划实际上意思就是计算的时候需要根据之前的结果来继续计算, 英文dynamic programming,动态编程的意思,在编程的时候本质上是枚举大量场景下的最优解,例如计算dp[a][b],的所有值,然后二维表,其中每个dp都是特定场景的最优解,但是我们可能最后只采用其中一个场景,计算其他场景的最优解是为了算出目标场景的最优解

解决动态规划问题可以分为四步

第一步 确定定义和状态

确定状态(描述一个场景要几维),然后转化为子问题(n推到n+1或者n-1)

什么是状态:所有会影响所定义的值(dp)计算的因素都是状态,但我们需要只选择最少且独立和必要的,如果两个状态可以互相推导,那么只选其中之一

注意这里的影响方式是影响某个选择的计算,而不是影响最最终的选择,最终选择哪个选择是进行取最值的操作或者其他逻辑操作。

例1->最大连续乘积,定义dp[n]是以arr[n]结尾的最大连续值,那么有从 dp[n-1] 到dp[n]有两种选择,一是直接arr[n]是最大连续值,二是dp[n-1]*arr[n]是最大连续值,但是你能保证 dp[n-1]*arr[n] 是你想要的最大值吗,万一arr[n]是负数,前面是正数,那他就不可能是dp的值,因此你要考虑加一个维度,记住dp[n]这个时候是正还是负数

例2->股票交易问题,定义dp[n]为第n天的利润,那么从dp[n-1]到dp[n]时有卖出和买入的选择,影响你计算卖出的是你之前买没买,没买那么就不能买,所以算的话还得加个维度,有没有买股票,另外有的题目还限制了交易次数,那么这个时候你能卖出吗?不能,因此,交易次数也是一个需要的状态

当然定义dp的时候很重要!!!跑偏了就会加大难度,你这边玩横看成岭侧成峰,别人一看横竖都是二氧化硅

例如最大连续乘积,常规做法,定义d[i][z]为以i结尾的最值z为0或者1表正负,

脑子不拐弯基本操作1:定义 dp[a][b] 表示从a连续乘到b的最大值,a和b确实足够描述和计算可能的最值,而且足够过了头,这样定义最值就是她的本身,没有其他计算逻辑,那么问题来了,你这么定义的话,从dp[a][b]推到到dp[a+1][b+1]很困难,不如直接算来得快,所以就变成

像上面的,虽然外表看着是dp这一套,但是已经偏离了dp的本质,因为上面的虽然可以计算出结果,但是没子问题一说,每个问题相互独立,不是动态规划,直接就是暴力枚举了

脑子不拐弯基本操作2:定义dp[a][b]为从a到b的最值,问题是怎么建立递推关系?dp[a][b]=???a+1还是b+1还是b-1窝巢。。怎么个顺序好,按二维数组的顺序?试试吧

dp[a][b]与dp[a][b-1]的关系。可能1:以arr[b]作为结果是dp[a][b]的连续最值,可能2:arr[b]*dp[a][b-1]的值是最值,我擦问题又来了。,乘出来是正是负?而且看起来,a好像没啥软用啊,所以又回到了基本操作

所以dp的定义很 很 很重要!!!!!!成功的一半,定义的时候想想有没有更简单的, 确定之后,定义了dp是什么,在后续的计算中,一定要时刻记住,dp的定义,不要多考虑什么上下文

第二步 写递推方程

写出状态转移方程,确定要求的值和状态转移方程的关系,写的时候发现维度不够就补多了就删

有可能是dp[0] 、dp[n]、max[dp[0…dp[n]],其他各种都可能

一个示例

dp[a][b][c]=max{ 用已经计算好的dp[x][y][z]计算选择A, 用已经计算好的 的dp[x][y][z] 计算选择B,… }

思考考递推式需要注意的点所有的选择的计算结果不一定正好是dp的值,但一定是可能成为dp的值 , 必须得有可能性,不然我拿一个Integer.MAX_VALUE塞进来给你做math.max?

第三步 条件和边界情况

初始条件和边界情况

1)把递推的初始结果先填了,可能是开始位置可能是中间位置可能是结束位置,也可能是其他的奇怪位置

2)根据方程,看计算顺序,重复一遍 有的题目比较变态,后面可能有n+1或者z-1,哪个维度是+的用从头到尾遍历,哪个维度是-的,那么for循环的时候用从尾到头遍历

第四步 写递推代码,取结果

写递推代码,取结果咯,一般这个比较简单,另外状态压缩什么的,如果发现每次都用n-1或者n+1,那么n-2 n+2的内容就可以不存。这就是状态压缩

附带几个视频教程,视频教程很有用,对入门很有用

https://www.bilibili.com/video/av45990457?from=search&seid=9856578185777231493

https://www.bilibili.com/video/av45990457?t=5558

数组遍历顺序举例

有时候动态规划会遇到遍历顺序的问题。

核心思想是: 看单数组的推导方向,看数组之间的约束条件,看badcase.,如:

最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

dp[left][right]=dp[left+1][right-1];

首先看两个参数的约束条件,left必定是小于等于right的,因此right放在外层循环,如果没有约束条件可以随意改变外内层

其次,right的推导顺序是小到大,因此是正向遍历,left的推导顺序是从大到小,因此是反向顺序

结合起来遍历顺序就是

然而这题即使两个都是正向遍历也可以得到正确答案!!原因在于递推式右边,在left+1的时候right-1以及有约束条件left<=right。如下图所示,由于right减1导致最终状态dp[left+1][right-1] 移动到了已经计算的上一行中

最长回文子序列

https://leetcode-cn.com/problems/longest-palindromic-subsequence/

得到的递推式是:

dp[l][r]=dp[l+1][r-1]+2; 和  dp[l][r]=Math.max(dp[l+1][r],dp[l][r-1]);

第二个递推式,由于没有r-1,导致正向遍历必定用到未计算的值,因此这个只能l反向,r正向。