DP相关题解

动态规划问题一般得满足：

1. 最优子结构
2. 无后效性
3. 子问题重叠

0x51 线性动规

eg1：Mr.Young’s Picture Permutations

题目分析

​ 本题是求有多少种安排合理的方案数。

​ 因为在合法的合影方案中每行、每列的身高都是单调的，所以我们可以从高到低依次考虑标记为 的学生站的位置。这样一来，在任意时刻，已经安排好位置的学生在每一行中占据的一定是从左端开始的连续诺干个位置，用一个元组 表示每一行已安排的学生人数，即可描绘出“已经处理的部分”的轮廓。

​ 当安排一名新的学生时，我们考虑所有满足如下条件的行号 ：

1. 。
2. 或 。

​ 只要该学生站在这样的一行中，每列学生的身高单调性也就得以满足。即我们不需要关心已经站好的名学生的具体方案。k元组描绘的轮廓内的合影方案总数就足以构成一个子问题。因此，我们可以把作为阶段，当安排一名新学生时，其中之一会增加1,从而转移到后续的阶段。

DP算法

​ 假设，表示各排从左端起分别站了个人时合理的方案数量。

• 边界：，其余均为0.
• 目标：.
• 转移：若$a_1a_2F[a_1,a_2+1,a_3,a_4,a_5]F[a_1,a_2,a_3,a_4,a_5]$。其他排同理。

题目总结（重要）

从该题给出的解法中我们发现，设计动态规划的状态转移方程，不一定要以“如何计算出一个状态”的形式给出，也可以考虑“一个状态应该更新哪些后续阶段的未知状态”。

eg2： 最长公共上升子序列

题目分析

​ 这道题目是 LIS 和 LCS 的综合，把二者结合很容易想到以下解法：

• 表示 ~ 与~ 可以构成的以为结尾的LCIS的长度。不妨假设 。
• 当时，有
• 当时，有

​ 显然上述的状态转移可以直接用三重循环的程序计算：

for i in range(1,n+1):
    for j in range(1,m+1):
        if a[i] != b[j]:
            f[i][j] = f[i-1][j]
            continue
        for k in range(j):
            if b[k] < a[i]:
                f[i][j] = max(f[i][j], f[i-1][k]+1)

​ 在转移过程中，我们把满足 的 构成的集合称为进行状态转移时的决策集合，记为。注意到，在第二层循环 从 1 增加到时，第一层循环 是一个定值，这使得条件 是固定的。因此，当变量增加1时，的取值范围从变为，即整数 可能会进入新的决策集合。也就是说，我们只需要地检查条件 是否满足，已经在决策集合中的数则一定不会被去除。

$$S(i,j+1)={ {S(i,j)\space\space\space\space\space B_j≥A_i}\brace{S(i,j)∪j\space\space\space\space B_j<A_i} }$$

​ 所以上面的状态转移方程只需要两重循环即可求解。最终目标是

for i in range(1,n+1):
    # val是决策集合S(i,j)中f[i-1][k]的最大值
    val = 0
    # j=1时，0可以作为 k 的取值
    if b[0] < a[i]: val = f[i-1][0]
    for j in range(1,m+1):
        if a[i] == b[j]: f[i][j] = val + 1
    	else: f[i][j] = f[i-1][j]
        # j:=j+1，检查 j 能否进入新的决策集合
        if b[j] < a[i]: val = max(val,f[i-1][j])

题目总结（重要）

​ 这道题转移部分的优化告诉我们，在实现状态转移方程时，要注意观察决策集合的范围随着状态的变化情况。对于“决策集合中的元素只增加不减少”的情况，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，把转移的复杂度降低一个量级。

eg3：Making the Grade

题目分析

引理：序列可能有“非严格单调递增”，“非严格单调递减”两种情况。以递增为例：

​ 我们发现在满足最小化的前提下，一定存在一种构造方案，使得中的数值都在中出现过。回到本题。我们一次考虑：完成前个数的构造时 的最小值。也就是把 DP 的“阶段”设为已经处理完的前缀序列的长度。在转移时，为了确定 定为多少我们才能保证单调，我们还需要知道 的大小。有两种常见的解决方案：

方法一：

​ 仿照 问题，设 表示完成前 个数的构造，并且 时， 的最小值。

$$F[i] = \underbrace{min\{F[j]+cost(j+1,i-1)\} }_{0≤j<i,A[j]≤A[i]}$$

​ 其中，$cost(j+1,i-1)$ 表示构造 $B_{j+1},…,B_{i-1}$ 同时满足 $A_j≤B_{j+1}≤…≤B_{i-1}≤A_i$ 时 $∑_{k=j+1}^{i-1}|A_j-Bj|$ 的最小值。

​ 该方法的解题思路是，最终 $B$ 序列由一段 $A$ 中的数构成。上面DP 中的 $i$ 就是当前最新一段数中与 $A$ 相同的位置，$j$ 是上一段数中这样的位置。因此，$cost(j+1,i-1)$ 就是把区间 $[j+1,i-1]$ 中前面的一部分变为 $A_j$ 后面的一部分变为 $A_i$，所需的最小代价。

注：我们不需要考虑中间某一部分数变为 $A_k$ 的情况，因为该情况已经被 $j=k$ 时覆盖。采用朴素算法计算 $cost$ 值，总的时间复杂度为$O(N^3)$。

方法二：既然仅把 DP 的“阶段”要素（即已经处理的序列长度）放在DP 状态中不足以执行转移，一个直接的想法就是把 $B$ 序列的最后一个值也记录在 DP 的状态里。设 $F[i][j]$ 表示完成前 $i$ 个构造，其中$B[i] = j$ 时 $S$ 的最小值。

$$F[i][j] = \underbrace{min\{F[i-1][k]+|A_i-j|\} }_{0≤k≤j}$$

​ 根据引理，我们可以把 序列中出现的数进行离散化，把 DP 状态中的第二维 的范围降低到 。另外，本题的转移与上题 十分类似，决策集合只增多不减少， 即可实现转移。故该题的时间复杂度为

思考题及扩展

eg4：Mobile Service

0x52 背包

eg1: 01背包例题：数字组合

f[0] = 1
for i in range(1, n+1):
    for j in range(m, a[i]-1, -1):
        f[j] += f[j-a[i]]

eg2：完全背包例题：自然数拆分

eg3：多个“体积维度”的0/1背包问题：陪审团

​