ZAFU ACM

Appearance

动态规划 ​

动态规划的“状态”和“转移”等概念可能较为抽象，也过于灵活，我列出了较多的例题帮助思考。

动态规划的难点在于状态设计和子结构的挖掘。

原理 ​

对于递推，我们可以做进一步抽象。

还是 Fibonacci 数列，我们把 Fi 称为一个状态。这个状态由 Fi−1 和 Fi−2 转移：

Fi=Fi−1+Fi−2

此公式称为动态转移方程，它描述了状态之间的关系。最后是边界 F1=F2=1。

很简单吧？来点基础模型。

矩阵取数 ​

给定一个 m×n 的矩阵 A（数字三角形也差不多），从左上角开始，只能向下或向右走，求路过所有数字之和最大值。

可以先思考一下，这道题怎么设状态比较好。

定义状态 F(i,j) 为停在位置 (i,j) 的所有路径中，路过数字之和的最大值。

而且由题知，一个位置只可能被从上面和左面过来。于是我们可以得到状态转移方程

F(i,j)=A(i,j)+max{F(i−1,j),F(i,j−1)}

即两者取大。边界是显然的 0。

状态 F(i,j) 具有最优子结构性，即它是走到 (i,j) 下的最优解，后续的解建立在前一个子结构上，自然也是最优解。

01 背包 ​

给定 n 个物品，第 i 个物品的体积为 Vi，价值为 Wi。有一容积为 M 的背包，求背包内能放下的最大价值。

设状态 F(i,j) 是从前 i 个物品中选出了总体积为 j 的物品放入背包后，放下的最大价值。

  • 若不选第 i 个物品，则 F(i,j)=F(i−1,j)。
  • 若选第 i 个物品且 j⩾i，则 F(i,j)=F(i−1,j−Vi)+Wi。

于是转移方程为两者取 max。边界自然为 0。

cpp
f[0][0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= m; j++)
    f[i][j] = f[i - 1][j];
  for (int j = v[i]; j <= m; j++)
    f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
f[0][0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= m; j++)
    f[i][j] = f[i - 1][j];
  for (int j = v[i]; j <= m; j++)
    f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}

滚动数组 ​

注意到阶段 i 只和上一阶段 i−1 有关。于是我们可以让数组滚动起来，重复利用，减掉一维。

然而在第 i 阶段内 j 的情况较复杂。F(i,j) 依赖于 F(i,j−Vi)，即依赖 j 是向前的，顺着循环前面先被更新，后面依赖的数据就没了。

怎么办？让循环倒着来，这样后面的先更新，前面不会被影响。

cpp
f[0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = m; j >= v[i]; j--) {
    f[j] = max(f[j], f[j - v[i]] + w[i]);
  }
}
f[0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = m; j >= v[i]; j--) {
    f[j] = max(f[j], f[j - v[i]] + w[i]);
  }
}

同样，矩阵取数也可以使用滚动数组。

完全背包 ​

给定 n 种物品，第 i 种物品的体积为 Vi，价值为 Wi，每种有无限个。有一容积为 M 的背包，求背包内能放下的最大价值。

自己尝试推一下，会发现正序循环恰好是所求解。

cpp
f[0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = v[i]; j <= v[i]; j++) {
    f[j] = max(f[j], f[j - v[i]] + w[i]);
  }
}
f[0] = 0;
for (int i = 0; i < n; i++) {
  for (int j = v[i]; j <= v[i]; j++) {
    f[j] = max(f[j], f[j - v[i]] + w[i]);
  }
}

最长公共子序列 ​

最长不下降子序列 ​

约瑟夫问题 ​

参考资料 ​

例题 ​