动态规划,千变万化。在此从易到难记录一些已经遇到过的问题。主要关注点:

  • 问题如何被拆解为多阶段决策(阶段)
  • 构造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]的最短路径值。用memset0x3e初始化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)(表示完成了ij的合并时的最小值),则将它更新为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”时能达到的最大值。
正确方法:用booldp[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型数组,也可以先将数组里的全部值赋为-1memset-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个乘号后的最优解。
Last modification:December 15th, 2019 at 09:25 am
如果觉得我的文章对你有用,请随意赞赏