浅谈我所理解的动态规划

5
(2)

前言

以前虽然知道动态规划,但是对于它的理解仅仅停留于背“状态转移方程”的阶段,随着我的理解和深入,我对这个问题有了更多的思考。

首先我的一个感受是,如果上来就去掌握状态转移方程,无后效性等、状态压缩及倒序循环、初始化等概念是不合适的,例如在某些"X分钟学算法"中告诉你求解动态规划很简单只需要四步1.问题拆解;2. 状态定义 3.递归方程推导 4. 实现…对于一个刚刚接触到动态规划的新手来说,这种教程是很不负责任的。

如何画马?1. 画两个圈 2. 画腿 3. 画脸 4. 画毛发 5. 再加一点小细节

这种”总结“看似帮助初学者掌握了动态规划的方法,但是实际上却仍只是浅浅的一层缺乏深入理解,此外对于动态规划中最关键的部分”状态转移方程推导“仍会使得很多新手望而却步。我自己也走过这些弯路,但是在无数次磕磕绊绊中,我对动态规划的认知之间加深,这篇一篇文章也是自己对于动态规划这个坑的小总结,同时也希望后来人不要再步入我的”磕磕绊绊“后尘,要想理解动态规划首先要从搜索和记忆化搜索讲起,因为动态规划的本质是记忆化搜索。

动态规划的本质是记忆化搜索

此外,如果没有重复子问题,动态规划往往会退化为搜索(暴力穷举),很多人认为“使用了动态规划就一定会降低时间复杂度“,其实并不是这样的。动态规划能够起到优化作用的前提条件是:具备重复子问题结构

Leetcode 91题解码方法为例,对于一个字符串 F("2213")=5, 可以分解为 F("213")和 F("13")两个子问题,在 F("213")这个子问题中又可以分为 F("13")和 F("3")两个子子问题,F("13")这个子子问题和 F("13")子问题是重复的,因而可以考虑使用记忆化搜索或动态规划来解决这个问题。同样地,动态规划也并非能够对所有的问题产生”记忆化“的作用:

Leetcode 91题解码方法为例,如果一个数中的一个前缀和两个前缀都是合法的,那么这个值就等同于斐波那契数列+1(,例如f("12121212")=Fibonaccic number(8+1) = 34 此时动态规划也就没有了意义(此时遍历了所有的解空间)

Leetcode 322题零钱兑换为例,倘若硬币组合是[2,4,8,16], 16, 则此时动态规划此时同样也没有起到优化的作用,因为在这该问题下,不具有重复的子结构(此时不存在重叠的子问题)

这也从侧面说明了,所有的动态规划,都能够通过DFS+记忆化搜索来实现,实际上记忆化搜索由于更加符合人的直觉,在某些问题上往往能够写出更加高效、易读的代码。

Leetcode 72题编辑距离为例,使用记忆化搜索很容易就能够把状态转移的关系表示出来,进而写出高效易读的代码。

最后总结一下,动态规划所有循环求解的问题都可以使用DFS深搜来解决,且只需要引入一个数组用来记录子问题的值(记忆化搜索)就能够达到和循环求解一样的时间复杂度。当然这句话说得有些绝对需要结合主定理来做进一步的分析,在由于某些语言中由于栈容量的限制N不能过大,但是倘若还能够使用合适的剪枝策略,记忆化搜索甚至还会超过循环求解(e.g. Leetcode 322零钱兑换)所以我们可以说:掌握了搜索就掌握了动态规划!

多状态

在一个问题中,往往具有多个状态,这些不同状态之间存在相互作用转化的关系,此时应该应该针对不同的状态开辟不同的数组。

Leetcode 121买卖股票的最佳时机为例,包含了两种状态:一种是当前状态下股票的最低价格,一种是当前状态下股票卖掉时能够获取到的最大利润。

Leetcode 309买卖股票的最佳时机含冷冻期为例,这里面包含了三个状态,需要我们梳理好这三个状态之间的关系。

针对多状态问题,只要我们好好体会不同状态之间的转化关系,绘制好状态转移图,根据状态转移图整理好不同状态之间的状态转移方程,就能够解决这类问题。

空间压缩(滚动数组)

由于某些动态转移方程所具有的性质,往往可以将空间复杂度降低一个时间复杂度级别。

Leetcode 198打家劫舍 为例,在该题目中,该题的状态转移方程为F[i] = max(F[i-1], F[i-2] + num[i]),根据状态转移方程可以得知,当前的状态仅由前一个状态和前两个状态有关,那么对于这个状态转移方程,我们只需要准备两个变量用来保存前一个状态和前两个状态的值,再利用辅助变量将问题的空间复杂度由之前的O(n)降低到O(1)。

Leetcode 322零钱兑换为例,零钱兑换(这道题和背包问题有相似之处)的状态转移方程是F[i][j] = max(F[i-1][j], F[i-1][j-coins[i]] + 1,如果根据这道题的状态转移方程来申请dp数组的话,我们应该选取的是M*N的二维数组,其中M是硬币的面值数,N是当前求得金额的值。从状态转移方程中,我们同样可以发现F[i][j]的值都是由F[i-1][*]也就是上一层的状态所决定。那么基于这个观察,我们就可以将空间复杂度从O(N^2)压缩到O(N)。

在某些情况下,为了避免F[i-1]被提前更新,需要将部分循环倒序处理。

倒序处理利用的是动态规划的无后效性,当然技巧与算法没有关系,只是帮助我们写出更加”巧妙“的代码。除了循环倒序处理以外,简单地,我们还可以额外引入一个数组临时,用来存储上一轮N-1循环的变量,然后在下一轮循环N后,再将第N论计算的数组覆盖到N-1临时数组上以备第N+1轮使用,如此反复……,这个技巧就是滚动数组

最后,空间压缩在某些问题无法使用,例如在LCS最长公共子序列等问题中不能降低空间复杂度。

坑1:初始化

对于动态规划,初始化的方式往往是一个坑,由于不同的题型往往会有不同的处理方式。虽然处理方式千奇百怪,但是在无数次的挣扎中,我也摸索出来了一些经验,我的经验是:如果当什么都不做的情况下,dp数组中每个解都是合法的,那么dp数组往往会初始化成0,如果当什么都不做的情况下,dp数组中每个解都是非法的,那么dp数组往往会初始化为INT_MAX或INT_MIN(视状态转移方程决定)

以0-1背包问题为例,如果最终题目要求可以不装满,那么则dp数组则初始化为0。如果要求恰好装满,那么此时只有容量为0的背包可以在什么都不装且截止为0的情况下被”恰好装满“,其他容量的背包没有合法的解,属于不合法的状态,因此要赋值为INT_MIN;如果要求背包并非被装满,那么任何容量的背包都存在一个合法的解”什么都不装“,这个合法的解对应的价值为0,所以初始状态的值也就是0了。

坑2:Padding

Padding是在动态规划循环求解中,为了避免对特例的处理保持循环的连续性(这一点和”Guard“(哨兵)的思想也是类似的,避免过多的条件判断)而引入的额外空间。

例如在背包问题中,对于dp[0]表示背包状态为0时的最大价值,我们知道完全背包问题的状态转移方程是F[i][j] = max(F[i-1][j], F[i-1][j- thisWeight] + thisValue), 如果不设置Padding的话,那么当j=1时,会引发越界异常,因而我们为0号元素分配一个空间以避免边界条件的处理。

对于Padding的初始化与坑1中的初始化是类似的,都有从实际问题出发,如果解是合法的,则初始化为0;如果不合法,则初始化为INT_MAX或INT_MIN

这篇文章是否对您有帮助?

请您为我打分吧!

平均分数 5 / 5. 投票数量: 2

发表评论

电子邮件地址不会被公开。 必填项已用*标注