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.co1in.me/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.co1in.me/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 15th, 2019 at 09:25 am © 允许规范转载 Support 如果觉得我的文章对你有用,请随意赞赏 Appreciate the author