动态规划,千变万化。在此从易到难记录一些已经遇到过的问题。主要关注点:
- 问题如何被拆解为多阶段决策(阶段)
- 构造DP数组的含义(状态)
- 状态转移方程(转移)
0 对动态规划适用条件的简单了解
- 条件1. 最优化原理(最优子结构性质)。所谓“一个最优化策略的子策略总是最优的”。
- 条件2. 无后效性。对未来状态的影响只能通过当前状态直接实现,而在当前状态之前的状态,它们是无法直接对未来状态产生影响的。也就是说,到达某个状态以后,未来只由当下决定。
对于条件1,可以这样理解:对于A→M→Z,A→Z的最优策略对于A→M也是最优策略。因为如果不是,存在另一种A→M的最优策略,那么将此替换前者,就找到了A→Z的更优策略,矛盾。
1 比较直接的转移
1.1 寻找网格中的“最短”路径值
问题
在给定矩阵中,从左上角走到右下角,只允许向右或向下走,求最短路径值。
(注:如果不规定“只允许向右或向上走”,会出现通过绕路来避开很长的一条边的情况)。
分析
对一个节点a[i][j]
,只能通过a[i-1][j]
或a[i][j-1]
转移达到,并且该问题符合两个条件。容易得到DP步骤:
- 初始化:输入矩阵
a[][]
,构造dp[i][j]
表示从左上角到达[i][j]
的最短路径值。用memset
配0x3e
初始化DP矩阵。(求最短,初始化为很大)令第一个点dp[1][1] = 0
。 - 状态转移方程:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]
2 枚举各个“阶段”的转移
2.1 枚举“中间点”
问题
多源最短路径问题:在给定图中,求任意两点之间的“最短”距离。
分析
此问题的算法是Floyd算法。具体见:
重点思想是最外层循环枚举中间点k,不断求出“允许”通过点ki转移的条件下的最优解,最后得到允许通过所有点转移的条件下的最优解。
因此,此题的“阶段”,即指允许通过k1转移是第一个阶段……允许通过ki点转移是第i个阶段;最后完成所有阶段。构造的DP数组中
dp[i][j]
表示从节点i
到节点j
的最短路径值。2.2 区间DP
问题
在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
(略作修改的问题:洛谷P1880)
分析
该题属于区间DP问题。该类问题是求解一段区间上的最优解,其子问题是求解子区间上的最优解。一般求解步骤为:
- 枚举子区间长度;
- 枚举子区间的“分割点”;
- 不断更新最优值。
因此对于“合并石子”问题,“阶段”指已经合并了len
堆。
显然根据len
划分下的分阶段决策符合条件1(设在某子区间上,有比最优策略的子策略更优的策略,则把前者换为后者,“最优策略”会更优)。
因为长度为len+1
的阶段只能由长度为len
的阶段直接转移得到,因此也符合条件2.
于是求解步骤为:
- 枚举已经合并的石子堆的总堆数(2~n)(一共n-1个阶段);
- 枚举合并区间起点
i
(则终点j
也能得到); - 枚举区间中的分割点
k
(“打擂台”寻找最小值):设当前状态为dp[i][j](i-j+1=len)
(表示完成了i
到j
的合并时的最小值),则将它更新为min(dp[i][j], dp[i][k] + dp[k+1][j])
,从而得到了区间长度为len
,起点为i
这个状态下的最优解。其实,这一步就是决策,从上一个阶段(有很多种)中的哪一个状态转移到当前状态是最优的。
3 不那么寻常的DP数组构造
3.1 bool型DP数组
问题
【洛谷P1877】一个初始值,经过n次操作后得到最终值,每次操作有一个操作数(op[i]
),操作不是当前值加操作数就是减操作数。要求在全过程中,该数值必须在[0, maxValue]
之间,求最终值的最大值。
分析
该题的难点在于DP数组的构造。
典型错例:机械模仿01背包,用dp[i][j]
表示“前i
次操作,最大值限制为j
”时能达到的最大值。
正确方法:用bool
型dp[i][j]
表示前i
次操作后,能否到达值j
。
于是步骤为:
- 初始化
dp[0][initial_value] = 1
- 状态转移:
if (dp[i - 1][j] == true)
if (j + op < maxValue) dp[i][j + op[i]] = true;
if (j - op > 0) dp[i][j - op[i]] = true;
3.2 01背包
问题
有N件物品和一个容量为V的背包。第i
件物品的费用(即体积,下同)是w[i]
,价值是val[i]
。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
分析
阶段:已经决策了i-1
件物品。
状态:dp[i][j]
表示,前i
件物品中挑出一些放入容量为j
的背包,此时物品的最大价值和。(子问题)
决策:当前第i
件物品是否要放入背包。
状态转移过程的合理性可以这样理解:只有子问题dp[i][j]
是最优解时,最终问题dp[N][V]
才可能是最优解。也就是说,dp[N][V]
的最优策略一定能使转移过程中的子问题dp[i][j]
最优。于是符合动态规划条件。具体转移过程即由上一个状态转移而来,分第i
件物品是否要放入背包两种情况。
于是有求解步骤:
- 遍历阶段
i
: 1~N - 遍历该阶段下背包大小
j
: 0~V - 状态转移:
if (w[i] <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + val[i]);
辨析
如果题目中的每个物品价值与重量成正比,那么问题就变为了求能装物品的最大重量,于是就可以仿照题目“调音”,用bool型数组记录能达到的重量值。但是,本题的价值与重量是独立的,若不改变思路,记录“能到达的价值”,那就得遍历1~sum_of_value
,即所有可能的价值,开这么大的数组显然是不行的。如果用int
记录到达j
重量时的价值,那最后结果是从整个dp[N][]
数组中寻找最大值,因为重量轻的可能反而价值大。略微改变思路,把“刚好达到j
重量”改为“不超过j
重量”,则dp[N][V]
就是最终结果。
当然,如果题目要求刚好装满背包,那就需要用前者的思路记录每个重量值是否能达到了。可以再开一个bool
型数组,也可以先将数组里的全部值赋为-1
(memset
为-1
即可),初始化dp[0][0] = 0
。状态转移:
dp[i][j] = dp[i - 1][j]; //not to choose
if (w[i] <= j)
if (dp[i - 1][j - w[i]] >= 0)
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + val[i]);
3.3 数字处理
问题
【洛谷P1018】向一个N位数字中插入K个乘号,求所得表达式的最大值。
分析
阶段(划分):已经放了多少个乘号。
状态:dp[i][j]
表示,前j
位放了i
个乘号时的最优解。
决策:第i个乘号放在哪?
状态转移:dp[i][j] = max(dp[i][j], dp[i - 1][k] * num[k + 1][j])
此题的状态转移枚举的是在前j
位里放第i
个乘号的位置k
;dp[i - 1][k] * num[k + 1][j]
的意思是在第k
位后面插入第i
个乘号,那么前j
个数(1~j)形成的表达式的值为:前k
个数里已经放过i-1
个乘号所形成的表达式的值 * 第k+1~j
位的连续数字形成的数值。
此题的难点在于将问题拆解为子问题。上述方法的巧妙之处在于:
- 在考虑插入第
i
个乘号时,是在之前已插入的所有乘号的最右侧插入新的乘号; - 因而插入新乘号后表达式的值等于它前面有
i-1
个乘号的表达式的值*
后面不含乘号的连续数字的值。 - 规定“最右侧”后,“在哪插入新的乘号”,假设是在第
k
个数字之后,就建立在了前k
位有i-1
个乘号的子问题上。 - 然后遍历
k
,取最优值,就得到了插入第i
个乘号后的最优解。