Loading... 动态规划，千变万化。在此从易到难记录一些已经遇到过的问题。主要关注点： - 问题如何被拆解为多阶段决策（阶段） - 构造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算法。具体见： <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.valderfield.com/archives/7/" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.valderfield.com/usr/themes/handsome/assets/img/sj/3.jpg);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">Floyd算法</p> <div class="inster-summary text-muted"> 背景程设作业题Week12-t1。给出一些单词，首尾字母形成首→尾的有向边，表明从首字母可以到达尾字母。问最后c能... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> 重点思想是最外层循环枚举中间点k，不断求出“允许”通过点ki转移的条件下的最优解，最后得到允许通过所有点转移的条件下的最优解。 因此，此题的“阶段”，即指允许通过k1转移是第一个阶段……允许通过ki点转移是第i个阶段；最后完成所有阶段。构造的DP数组中`dp[i][j]`表示从节点`i`到节点`j`的最短路径值。 ##2.2 区间DP ###问题 在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。 （略作修改的问题：[洛谷P1880][1]） ###分析 该题属于区间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][2]】一个初始值，经过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][3]】向一个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`个乘号后的最优解。 [1]: https://www.luogu.com.cn/problem/P1880 [2]: https://www.luogu.com.cn/problem/P1877 [3]: https://www.luogu.com.cn/problem/P1018 Last modification：December 15, 2019 © Allow specification reprint Support Appreciate the author Like 0 如果觉得我的文章对你有用，请随意赞赏