动态规划基础

| | nedchu

简介

动态规划(Dynamic Programming or DP)是运筹学的一个分支，用于解决一些最优决策的问题。在程序设计竞赛和公司面试中动态规划都是十分重要的知识点，主要原因在于动态规划思维灵活多变，形式多样，容易和各类知识结合。程序设计竞赛中，动态规划题目出现比较频繁，解法常常不止一种，能出简单的题也能出很难的（难题中一般是解法的一部分），是从入门开始就要修炼的技能。通过动态规划的训练，能够更加熟练地运用递归思想，接近算法思维的核心。由于有递归思想在其中，很多同学在刚接触dp时会觉得摸不到头脑，感觉是玄学，在经过深入的训练之后，就能更熟练地掌握dp了，跟其他算法比起来，dp属于最为需要实战训练的算法，通过学习各种dp模型才能够好地掌握dp。

什么是dp

基本性质

dp其实跟动态没啥关系，本质上是一种记录结果重用的技术，我常称dp为暴力，其实dp的确是一种比较优雅精巧的暴力，拿空间换取时间。

dp的问题主要有以下性质：

  • 最优子结构：一个问题的最优解能够使用其他相似的问题的最优解得到。
  • 重叠子问题：一个问题会被计算多次。

  • 无后效性：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。

    性质举例

    以下的例子虽然不算是dp，但是可以展示出dp大致是什么。主要以斐波那契数列$Fib_i=Fib_{i-1}+Fib_{i-2}(i>1,Fib_0=Fib_1=1)$的求解为例子。

  • 最优子结构：一个问题的最优解能够使用其他相似的问题的最优解得到。比如对于斐波那契数列，$Fib_i,Fib_{i-1},Fib_{i-2}$分别对应了参数为$i, i-1,i-2$的斐波那契数列求解问题，这三个问题参数不同却是在解决同一个问题，所以是相似的问题。而我们能够通过后两个问题的结果直接加和获得第一个问题的结果，也就能用相似问题的解获得该问题的最优解了。

  • 重叠子问题：一个问题会被计算多次。比如递归展开后$Fib_{i-2}$会在$Fib_i,Fib_{i-1}$中被计算，那么如果能把$Fib_{i-2}$的结果保留下来，就能在计算中直接使用结果，从而加速计算，这点是动态规划与分治算法的主要区别，分治中不存在重叠的子问题

  • 无后效性：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。对斐波那契数列来说，就是对于一个固定的$i$来说$Fib_i$是不变的，只需要求解一次。我觉得更形象的理解是解之间的依赖关系形成了一张有向无环图，能根据拓扑序来求解，当然这种理解需要了解一些图论的知识。有后效性的一个例子就是一个棋盘上有个棋子四个方向等概率走，从某个位置开始，求第一次到某个位置的期望步数，容易发现到某位置的期望是到周围四个位置的期望的平均值，可以发现这个例子中一个位置的期望展开后会依赖到它自己，会不断更新，不满足无后效性的条件。

总的来说最优子结构保证了问题能够得到求解，重叠子问题是重复利用结果也是加速的基础，无后效性保证了结果只需要求一次，于是按照特定的顺序（解依赖的拓扑序），我们能够通过之前记录的结果求出逐个求出所有问题的解。

dp的两种形式

动态规划主要基于递归的思想，而展现的形式主要有两种，分别是递推和记忆化搜索，这两种方法各有各的特点，也能够相互之间转化，需要根据题目的具体特性选择合适的方法来进行求解。

第一种方式是递推，一般是根据循环直接获得结果，需要注意计算的顺序必须要满足解之间的依赖，即被依赖的解要先计算。对于斐波那契数列来说，递推的形式如下：

1
2
3
4
f[0] = f[1] = 1; // 1. 边界条件
for (int i = 2; i < n; i++) {
  f[i] = f[i-1] + f[i-2]; // 2. 递推关系
}

第二种方式是记忆化搜索，一般通过搜索的方式获得结果，求解的步骤是首先将数组中的值标记为不可能的值(-1,0x3f3f3f3f之类的)，搜索时若记录的数组中对应的值是不可能的值就求解该问题，并将结果记录在数组中，若对应的值是可能的值说明已经计算过该值，可以直接返回结果。记忆化搜索相对来说流程比较复杂，例子和流程如下：

1
2
3
4
5
6
7
8
9
10
11
int dfs(int x) {
  if (f[x] != -1) return f[x]; // 2. 若不是不可能的值，说明已经计算过，直接返回，保证空间中的每个值只会被计算一次
  if (x <= 1) return f[x] = 1; // 3. 边界条件也可以在搜索过程中直接给出
  return f[x] = dfs(x-1) + dfs(x-2); // 4. 求解问题并进行记录，注意要调用函数而非取数组的值
}

int main() {
  memset(f, -1, sizeof f); // 1. 初始化记录数组为不可能的值
  f[0] = f[1] = 1; // 3. 边界条件可以在初始化后直接给出
  printf("%d\n", dfs(10)); // 5. 调用
}

从时空复杂度来说两者并没有差别，但各自有不同的特点。递推代表了自底向上，记忆化搜索代表了自顶向下。递推比较适合依赖关系简单的问题，写起来比较简洁，当依赖复杂时容易出错。记忆化搜索写起来长一些，调用程序栈也会有一些花销，好处是不用关注依赖关系，直接调用函数即可。

dp的复杂度

dp的空间复杂度和解状态的空间有关了。

dp的时间复杂度与两个变量相关，首先是空间复杂度，因为每个值会被计算一次，其次就是每个值利用已有的解进行构建的复杂度，注意此处只考虑构建的复杂度，已有解的计算复杂度不必考虑。由于每个值的计算就是通过已有解来构建，而且每个值只计算一次，所以最终的复杂度就是两者的乘积。

dp的时空复杂度相对来说容易计算，许多问题灵活多变，会有多种时空复杂的解法。在时空复杂度不符合题目需求时，需要考虑改变状态的意义，合理进行剪枝或者使用堆，线段树，树状数组，平衡树等高效数据结构进行优化。

dp与分治和贪心

解决最优化问题的手段很多，除了dp以外，分治和贪心也是其中非常重要的手段，本节主要讨论他们之间的异同。

常见的分治算法有：二分，快速排序，归并排序，FFT，最近点对，线段树等等。分治的核心思想是分而治之，将问题划分成若干个不相交的类似子问题，解决他们之后，再将结果不断合并。dp和分治的最大不同点在于：dp中问题的求解之间有重叠，结果被保存下来，多次重复使用，而分治之中问题的结果通常不用保存，因为所有求解的问题之间是没有重叠的，比如我们不会在排序时对某个区间排序两次。分治和dp都运用了递归的思想，利用类似的问题的结果获得目标的结果，核心思想非常接近。

常见的贪心算法有：哈弗曼编码，Kruskal等等。贪心非常常见，因为它简单高效，实质上贪心就是只考虑当下一步步获得最优解。dp和贪心的不同在于：dp考虑的是多种决策方式下的最优，而贪心的决策方式是唯一的。贪心的构造方式是一条链，而dp是一张更为复杂的图。dp可以看做是一种更高层次的，考虑更周全的贪心，以多种决策的最优解来贪心构造。

0-1背包问题

背包问题是动态规划最为基础的模型。有一个能容纳重量 $W$ 的背包，有 $n$ 种物品每种只有一个，要么取要么不取，第 $i$ 个物品的重量和价值为 $w_i,v_i$，希望找到一个方案，在背包内容纳价值之和尽量高的物品。

容易想到可以$O(2^n\cdot n)$枚举所有方案取最大值，以及搜索时候进行巧妙简直，这类方案复杂度过高，只能处理规模很小的数据。另外一种常见的思路是尝试利用贪心解决问题，为了举一个简单的反例，此处首先简化问题为重量和价值相同，问题变为在背包里容纳尽量重的物品，若背包大小为$6$，物品重量分别为$5~3~3$，贪心先取出大的就会出现问题。

使用dp解决背包时，第一维代表使用前$i$种物品，第二维是重量，$dp[i][j]$是使用前$i$种物品总重量为$j$时的最大价值。想要获取$dp[i+1][j]$，在考虑一个新物品时有两种决策方式，如果最新的物品不取，则需要求得使用前$i$个物品总重量为$j$时的最大值，即$dp[i][j]$，如果最新的物品取用，总重量需要占去一部分，剩余$j-w[i]$空间需要用前$i$种物品获得尽量大的价值，这部分价值还需要加上最新物品的价值，决策的结果为$dp[i][j - w[i]] + v[i]$，整理之后可以获得如下代码：

1
2
3
4
5
6
7
8
9
10
11
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= W; j++) {
    if (j < w[i]) {
      dp[i + 1][j] = dp[i][j];
    } else {
      dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
    }
  }
}
dp[n][W] is answer.

一个常见的优化是将数组变化为一维，意义为重量，第二层遍历时反向遍历，这么做以后所有当前的$j$以后的值都是本轮更新过的，而之前的值都是上一轮的结果，没有更新过的是$dp[i][\cdot]$更新过的是$dp[i+1][\cdot]$，由于一般保证重量是正数，更新使用的状态恰好符合了简化前的要求，简化后代码如下：

1
2
3
4
5
6
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++) {
  for (int j = W; j >= w[i]; j--) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  }
}

容易发现以上算法的复杂度为$O(nW)$，相比枚举算法的$O(2^n\cdot n)$有了极大的改进，而代码反而更短，这也正是dp的魅力和威力所在。0-1背包问题是最基础的动态规划问题，由于物品只有一个取就是1不取就是0，所以被称为0-1背包。除此之外还有很多背包问题变种比如完全背包和多重背包，此处不再过多展开，有兴趣的同学可以进一步查阅一份网上的教程叫做《背包九讲》。

0-1背包条件的变化

上一节的基础0-1背包算法中，算法的时空复杂度为$O(nW)$，这里其实我们假定了问题中个数和背包的容量不是非常大，可并不是所有问题满足这样的条件。假定有一道问题中，个数和价值不是非常大，而背包容量很大，莫非dp就没用了嘛？实际此时我们只需要重新构建新的dp意义就能再次利用dp解决这个问题了。

新的dp意义中，第一维代表使用前$i$种物品，第二维是总价值，$dp[i][j]$是使用前$i$种物品总价值为$j$时的最小重量。想要获取$dp[i+1][j]$，在考虑一个新物品时有两种决策方式，如果最新的物品不取，则需要求得使用前$i$种物品总价值为$j$时的最小重量，即$dp[i][j]$，如果最新的物品取用，总价值已经满足了一部分，剩余$j-v[i]$价值需要用前$i$种物品以尽量小的重量满足，这部分重量还需要加上最新物品的重量，决策的结果为$dp[i][j - v[i]] + w[i]$，取用两种决策的最小值。

和上一个算法不同，此次要求的是最小值，因而初始化整个数组为很大的整数，初始条件是价值为0时最小重量为0，最终若$dp[n][i]\leq W$则对应的$i$价值能够用容量为$W$的背包达到，令$V=\sum v_i$，则算法复杂度变为$O(nV)$，将代码做了压缩的优化后如下：

1
2
3
4
5
6
7
8
9
10
11
12
const int INF = 0x3f3f3f3f;
memset(dp, INF, sizeof dp);
dp[0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = V; j >= v[i]; j--) {
    dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
  }
}
int ans = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] <= W) ans = i;
}

dp的回溯

dp中有部分问题需要输出最优解的构成，比如输出最短路的路径或者输出最优方案。上述操作我们称之为回溯，完成回溯需要在dp过程中加入额外的代码。通常来说可以储存状态转移的来源，开辟一个和状态结构相同的空间，在发现更优结果更新dp值的同时更新来源。在0-1背包问题中，若要进行回溯就不能进行数组压缩，具体原因可以自行尝试并考虑。

由于值都是从上一行转移过来的，只需要记录第二维的信息。当不取用物品时，来源就是上一维的$j$，若取物品则来源是上一维的$j-w[i]$，在决策的同时根据决策更新来源值。如此一来，当$j\neq bk[i][j]$时就知道决策至该状态时选择了加入物品，状态是从$dp[i-1][bk[i][j]]$更新而来，利用一个值不断迭代重量即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= W; j++) {
    dp[i + 1][j] = dp[i][j];
    bk[i + 1][j] = j;
    if (j >= w[i] && dp[i][j - w[i]] + v[i] > dp[i + 1][j]) {
      bk[i + 1][j] = j - w[i];
    }
  }
}
vector<int> res;
int cur = W;
for (int i = n; i >= 1; i--) {
  if (cur != bk[i][cur]) res.push_back(i-1);
  cur = bk[i][cur];
}

dp常见模型

  1. 完全背包，多重背包，都是基于0-1背包拓展的问题，具体可以查看经典教程《背包九讲》
  2. 最长公共子序列(Longest Common Subsequence)
  3. 最长上升子序列(Longest Increasing Subsequence)，有简单的 $O(n^2)$ 解法和更快的 $O(n\log n)$ 解法
  4. 最长子段和，有分治的 $O(n\log n)$ 解法和dp的线性解法，这个算法能够进一步去求解最大子矩阵问题
  5. 区间上的问题，常见的有回文切割及回文相关的问题

dp的模型灵活多变，一个问题也可以有多种解决方案，这里只列举了一些比较常见和简单的模型，不进行详细的展开，如有机会将再写文章专门讨论。相关的题目会附在之后的习题推荐中。

习题推荐

  • hdu 2602 0-1背包
  • hdu 1159 LCS
  • open 2533 LIS
  • poj 3280 回文
  • hdu 1003 最大子段和
  • URAL 1078 回溯
  • hdu 1025 LIS
  • 51nod 1051 最大子矩阵
  • cf 1025D