• 基础动态规划
  • 背包模型
    • 01背包
      • 题目模型
      • 题目特点
      • 状态表达式和状态转移方程
      • 实现
      • 复杂度分析
      • 优化！
    • 完全背包
      • 题目模型
      • 题目特点
      • 状态表达式和状态转移方程
      • 复杂度分析
      • 优化！转化成01背包！
      • 再优化！
    • 多重背包
      • 题目模型
      • 题目特点
  • 最长公共子序列（LCS）
    • 题目模型
    • 分析
  • 最长上升子序列
    • 题目模型
    • 分析

基础动态规划

基础动态规划模型：

1. 背包模型
2. 最长公共子序列
3. 最长上升子序列

背包模型

背包模型构成了动态规划中的一大类问题。比赛中的很多问题都是通过背包模型变形得到的。所以，背包模型在基础的 dp 里是非常重要的一部分。

01背包

01背包是所以背包问题的基础，所有和背包相关的问题都能找到01背包的影子。01背包问题可以被一般化为这样的一个模型。

题目模型

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 个物品的体积和价值分别是 $C_i$ 和 $W_i$ 。求解将哪些物品放进包里可以使价值最大。

题目特点

这类题目的很明显的特点是，每个物品都只有一个，可以选择要或者不要。

状态表达式和状态转移方程

状态表达式：$dp[i][j]$ 去表示前 $i$ 个物品恰好放入一个容量为 $j$ 的背包里所得到的最大的价值。
状态转移方程：$dp[i][j] = max(dp[i-1][j], dp[i-1][j-C_i]+W_i)$

这里很显然的是，max表达式的前半部分表示的是不选择第i个物品的情况，而后半部分表示的是选择了第i个物品的情况。

实现

for (int i = 0; i <= V; i++) dp[0][i] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = C[i]; j <= V; j++) {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-C[i]]+W[i]);
    }
}

复杂度分析

时间复杂度：$O(NV)$
空间复杂度：$O(NV)$

优化！

这里的时间复杂度已经没有办法再优化了，可是空间复杂度却还有优化的余地。考虑我们的第二层循环，这里的每一个dp[i][j]的取值是都只和第二维比j小的元素有关。那么是否可以通过改变枚举方向的方式，来把第一维用来保存当前位置的一列删掉呢。显然是可以的。考虑这样的代码：

for (int i = 0; i <= V; i++) dp[i] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = V; j >= C[i]; j--) {
        dp[j] = max(dp[j], dp[j-C[i]]+W[i]);
    }
}

这里唯一的变化是改变了j的枚举方向。可以仔细思考一下。

完全背包

题目模型

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 个物品的体积和价值分别是 $C_i$ 和 $W_i$ 。每个物品能无限制的使用任意个。求解将哪些物品放进包里可以使价值最大。

题目特点

大体和01背包类似，唯一不同的地方是每种物品有无限个。此时每种物品的策略已经不再是要或者不要了，而变成了要0个，要1个，要2个……

状态表达式和状态转移方程

状态表达式方面和01背包是一样的，依旧用$dp[i][j]$ 去表示前 $i$ 个物品恰好放入一个容量为 $j$ 的背包的最大价值。我们就可以很容易的按照原本的思路，写出状态转移方程：$dp[i][j] = max_{0 \leq kC_i \leq V}\{dp[i-1][V-kC_i]+KW_i\}$

复杂度分析

时间复杂度：$O(NV\sum\frac V{C_i})$
空间复杂度：$O(NV)$

优化！转化成01背包！

01背包是所有背包的基础，也就是说所有的背包相关问题都能被转化成01背包的模型。即比如说这个问题，如果把每个物品不当成是无限个的，而是最多有$\lfloor \frac V{C_i} \rfloor$件的话，就可以把一种东西拆成$\lfloor \frac V{C_i} \rfloor$件东西。然后就可以被转化成了而基础的01背包问题。这是这种方法的时间复杂度和上面的方法是一样的，也是不能接受的。我们需要一个更加高效的拆分方法。

这里应该很容易就可以考虑到我们经常运用到的和二进制有关的拆分方法，也就是把第$i$种物品拆成费用为$C_i2^k$，价值为$W_i2^k$的若干件物品。这样每种物品不再被拆成了$\lfloor \frac V{C_i} \rfloor$个，而是$\log_2\lfloor \frac V{C_i} \rfloor$个。

再优化！

考虑下面这样的代码：

for (int i = 0; i <= V; i++) dp[i] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = C[i]; j <= V; j++) {
        dp[j] = max(dp[j], dp[j-C[i]]+W[i]);
    }
}

可以看到，这段代码和01背包的空间优化版本是不是特别像？对的。首先要考虑在01背包中第二层循环是$V \to C_i$的原因，因为每件物品都只有一个，当前的选择不能被前面的选择所影响，如果是按照$C_i \to V$的顺序的话，当计算到一个值的时候，前面所用到的$j-C[i]$的这个值可能是已经选择了当前物品的情况，所以用来先计算体积大的部分（因为无后效性）。
而在这个问题中，显然是应该被前面计算的值所影响的，因为每件物品有无限个。这个应该很容易理解到。

多重背包

题目模型

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 个物品的体积和价值分别是 $C_i$ 和 $W_i$ 。每个物品最多只有 $M_i$ 个物品可用。求解将哪些物品放进包里可以使价值最大。

题目特点

和完全背包很相似，唯一不同的地方就是每个物品的最大个数不再是 $\frac V{C_i}$，而变成了 $min(\frac V{C_i},M_i)$。其他的部分都和完全背包是一样的。

关于背包的其他问题，可以参考背包九讲。

最长公共子序列（LCS）

题目模型

给定两个序列 $X=\langle x_1, x_2, \ldots, x_m\rangle$ 和 $Y=\langle y_1, y_2, \ldots, y_n\rangle$，求 $X$ 和 $Y$ 的最长公共子序列。

• 一个给定序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。
• 给定两个序列 $X$ 和 $Y$，如果 $Z$ 既是 $X$ 的子序列，又是 $Y$ 的子序列，我们称它是 $X$ 和 $Y$ 的公共子序列。

分析

首先是阶段的划分，我们把这两个序列的一个前缀，作为一个阶段。那么我们可以得到阶段的表示 $C[i][j]$ 。表示了，序列 $X_i$ 和 $Y_j$ 的LCS。（前缀的定义：给定一个序列 $X=\langle x_1, x_2, \ldots, x_m\rangle$，对应的 $i=0,1,\ldots,m$，定义 $X$ 的第 $i$ 前缀 $X_i=\langle x_1, x_2, \ldots, x_i\rangle$。）

按照这个阶段的划分，再来讨论这个问题是否存在最优子结构。这个显然是存在的。

定理1（LCS的最优子结构） 令 $X=\langle x_1, x_2, \ldots, x_m\rangle$ 和 $Y=\langle y_1, y_2, \ldots, y_n\rangle$ 为连个序列，$Z=\langle z_1, z_2, \ldots, z_k\rangle$ 为 $X$ 和 $Y$ 的任意 LCS。

1. 如果 $x_m=y_n$，则 $z_k=x_m=y_n$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个LCS。
2. 如果 $x_m \neq y_n$，那么 $z_k \neq x_m$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个LCS。
3. 如果 $x_m \neq y_n$，那么 $z_k \neq y_n$ 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的一个LCS。

满足了最优子结构之后，显然是满足无后效性的。最后我们要思考的问题，就是是否有重叠子问题。从上面的定理我们可以发现，在求 $X=\langle x_1, x_2, \ldots, x_m\rangle$ 和 $Y=\langle y_1, y_2, \ldots, y_n\rangle$ 的 LCS 的时候，我们需要求解一个或两个子问题。

1. 如果 $x_m=y_n$，我们就要求解 $X_{m-1}$ 和 $Y_{n-1}$ 的一个LCS。然后把 $x_m=y_n$ 追加到这个序列的末尾。
2. 如果 $x_m \neq y_n$，我们就要求分别求解 $X_{m-1}$ 和 $Y$ 的一个 LCS ，和 $X$ 和 $Y_{n-1}$ 的一个LCS。并取较长的一个。

上面的全部分析，已经足以让我们得到状态表达式和状态转移方程了。这里就不说下去了。相信自己一定可以写出来。

最长上升子序列

最长上升子序列的问题，使用dp的解法并不是最优的。这里只是展示一个dp的思路。（作为一个dp的例题，希望可以帮助理解dp的基础内容。）

题目模型

给定一个序列 $X=\langle x_1, x_2, \ldots, x_m \rangle$，求 $X$ 的一个最长的子序列 $Y=\langle y_1, y_2, \ldots, y_n \rangle$，满足 $y_1 < y_2 < \ldots < y_n$。

分析

这个问题和上个问题有点不一样的地方是，我们对于阶段的划分不能简单的使用这个序列的前缀，因为只考虑一个前缀的最长上升子序列的话，是不能知道是否应该把当前要考虑的元素添加到一个前缀的最长上升子序列的末尾的。

所以，我们需要在状态的设计之中加入有关于一个最长上升子序列的最末尾元素的信息。（因为只要知道最末尾元素是什么，就可以判断当前元素是否可以被接在这个序列的后面了。）由此，状态的表达就变成了：$dp[i]$ 来表示以 $x_i$ 结尾的最长上升子序列的长度。

那么我们来考虑刚才说的状态转移， $dp[i] = max_{1 \leq j < i, x_j < x_i}\{dp[j]\}+1$。