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

• 问题如何被拆解为多阶段决策（阶段）
• 构造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算法。具体见：

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个乘号后的最优解。