动态规划专题_动态规划方法所耗时间和空间远小于朴素解法

动态规划（Dynamic programming，简称 DP）通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
严格意义上，动态规划只能用来解决最优化问题，但在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

动态规划基础

动态规划应用于子问题重叠的情况：

1. 要去刻画最优解的结构特征；
2. 尝试递归地定义最优解的值（就是我们常- 说的考虑从 转移到 ）；
3. 计算最优解；
4. 利用计算出的信息构造一个最优解。

钢条切割

给定一段钢条，和不同长度的价格，问如何切割使得总价格最大。
为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的子问题。 即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。 我们通过组合相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。

最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

动态规划的两种实现方法：

• 带备忘的自顶向下法（记忆化搜索）；
• 自底向上法（将子问题按规模排序，类似于递推）。

算导用子问题图上按照逆拓扑序求解问题，引出记忆化搜索。
重构解（输出方案）：转移的时候记录最优子结构的位置。

矩阵链乘法

给出 n个矩阵的序列，希望计算他们的乘积，问最少需要多少次乘法运算？

（认为$p\times q$ 的矩阵与$q\times r$ 的矩阵相乘代价是$p\times q\times r$ 。）
完全括号化方案是指要给出谁先和谁乘。

动态规划原理

两个要素：

最优子结构

具有最优子结构也可能是适合用贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题。

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，你界定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
   给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
3. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。
4. 要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题；
   确定最优解使用哪些子问题时，需要考察多少种选择。
2. 子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

经典问题：

• 无权最短路径： 具有最优子结构性质。
• 无权最长（简单）路径： 此问题不具有，是 NPC 的。区别在于，要保证子问题无关，即同一个原问题的一个子问题的解不影响另一个子问题的解。相关：求解一个子问题时用到了某些资源，导致这些资源在求解其他子问题时不可用。

子问题重叠

子问题空间要足够小，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。

重构最优解

存表记录最优分割的位置，就不用重新按照代价来重构。

最长公共子序列

子序列允许不连续。

每个$c[i][j]$ 只依赖于$c[i-1][j]$ 、 $c[i][j-1]$ 和 $c[i-1][j-1]$ 。

记录最优方案的时候可以不需要额外建表（优化空间），因为重新选择一遍（转移过程）也是 $O(1)$ 的。

最优二叉搜索树

给二叉搜索树的每个节点定义一个权值，问如何安排使得权值和深度的乘积最小。
考虑当一棵子树成为了一个节点的子树时，答案（期望搜索代价）有何变化？

由于每个节点的深度都增加了 1，这棵子树的期望搜索代价的增加值应为所有概率之和。

tD/eD 动态规划： 状态空间是 $O(n^t)$ 的，每一项依赖其他$O(n^e)$ 项。

最长连续不下降子序列

我们的目标是求出给定序列的一个最长的连续子序列，满足这个序列中的后一个元素 不小于 前一个元素。

因为是连续的，所以只要与上一个元素进行比较即可。

int a[MAXN];
int dp() {
  int now = 1, ans = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] >= a[i - 1])
      now++;
    else
      now = 1;
    ans = max(now, ans);
  }
  return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

最长不下降子序列

与最长连续不下降子序列不同的是，不需要这个子序列是连续的了。

求最长子序列的方法有两种。
最简单的第一种$O(n^2)$的算法。每一次从头扫描找出最佳答案。

int a[MAXN], d[MAXN];
int dp() {
  d[1] = 1;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++)
      if (a[j] <= a[i]) {//判断j能否添加到该序列中
        d[i] = max(d[i], d[j] + 1);//是否将j添加到该序列中
        ans = max(ans, d[i]);
      }
  }
  return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

稍复杂的第二种$n$ long $n$的算法， 参考了这篇文章

首先，定义 $a_1......a_n$为原始序列， d为当前的不下降子序列， len为子序列的长度，那么$d_{len}$ 就是长度为 len 的不下降子序列末尾元素。

初始化：$d_1=a_1、len=1$。

现在我们已知最长的不下降子序列长度为 1，那么我们让 i 从 2 到 n循环，依次求出前 i个元素的最长不下降子序列的长度，循环的时候我们只需要维护好 这个数d组还有 len就可以了。关键在于如何维护。

考虑进来一个元素$a_i$ ：

1.元素大于等于 $d_{len}$，直接$d_{++len}=a_i$ 即可，这个比较好理解。
元素小于$d_{len}$ ，找到 第一个 大于它的元素，插入进去，其他小于它的元素不要。
那么代码如下：

for (int i = 0; i < n; ++i) scanf("%d", a + i);
memset(dp, 0x1f, sizeof dp);
mx = dp[0];
for (int i = 0; i < n; ++i) {
  *std::upper_bound(dp, dp + n, a[i]) = a[i];
}
ans = 0;
while (dp[ans] != mx) ++ans;
1
2
3
4
5
6
7
8

经典问题（来自习题）

DAG 中的最长简单路径

$dp[i]=max(dp[j]+1)((i,j)\in E)$

最长回文子序列

$dp[i][i+len]$=$\{{}_{max(dp[i+1][i+len],dp[i][i+len-1]),else}^{dp[i+1][i+len-1]+1,ifs[i]=s[i+len]}$
边界：$dp[i][j]=1$。

注意： $dp[i][j]$表示的是闭区间。

也可以转化为 LCS 问题，只需要把a 串反转当做b ，对 a和 b求 LCS 即可。
注意区分子串（要求连续）的问题。

最长回文子串

$O(n^2):dp[i]=max(dp[j]+1,dp[i]),s(j+1...i)$是回文

$O(n)$：Manacher

p[i]表示从i 向两侧延伸（当然要保证两侧对应位置相等）的最大长度。

为了处理方便，我们把原串每两个字符之间加一个（不包含在原串中的）#，开头加一个 $。

这样得到的回文串长度就保证是奇数了
考虑如果按顺序得到了$p[1...i-1]$ ，如何计算p[i] 的值？
如果之前有一个位置比如说是id ，有 p[id]+id>i那么 i 这个位置是被覆盖了的，根据id 处的对称性，我们找$p[id\times 2-i]$ 延伸的部分被p[id] 延伸的部分所覆盖的那段，显然这段对称回去之后是可以从i 处延伸出去的长度。
如果找不到呢？就先让p[id]=1 吧。
之后再暴力延伸一下.
可以证明是$O(n)$ 的。
至于如何找是否有这么一个 id 呢？递推的时候存一个max 就好了。

当选取的状态难以进行递推时（分解出的子问题和原问题形式不一样），考虑将问题状态分类细化，增加维度。

记忆化搜索

(1)How many ways HDU - 1978（记忆化搜索关于求多少种方式模板）
(2)FatMouse and Cheese HDU - 1078（记忆化搜索入门模板）

记忆化搜索的特征：

1. 不依赖任何 外部变量
2. 答案以返回值的形式存在，而不能以参数的形式存在（就是不能将 dfs 定义成 dfs(pos,tleft,nowans)，这里面的 nowans 不符合要求）。
3. 对于相同一组参数，dfs 返回值总是相同的

如何写记忆化搜索

方法一

1. 把这道题的 dp 状态和方程写出来
2. 根据它们写出 dfs 函数
3. 添加记忆化数组

$dp[i]=max(dp[i],dp[j+1])(最长上升子序列)$

int dfs(int i) {
  if (mem[i] != -1) return mem[i];
  int ret = 1;
  for (int j = 1; j < i; j++)
    if (a[j] < a[i]) ret = max(ret, dfs(j) + 1);
  return mem[i] = ret;
}
int main() {
  memset(mem, -1, sizeof(mem));
  // 读入部分略去
  cout << dfs(n) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

方法 II

1. 写出这道题的暴搜程序（最好是 dfs)
2. 将这个 dfs 改成“无需外部变量”的 dfs
3. 添加记忆化数组

山洞里有 M株不同的草药，采每一株都需要一些时间$t_i$ ，每一株也有它自身的价值$v_i$ 。给你一段时间 T，在这段时间里，你可以采到一些草药。让采到的草药的总价值最大。

int n, t;
int tcost[103], mget[103];
int ans = 0;
void dfs(int pos, int tleft, int tans) {
  if (tleft < 0) return;
  if (pos == n + 1) {
    ans = max(ans, tans);
    return;
  }
  dfs(pos + 1, tleft, tans);
  dfs(pos + 1, tleft - tcost[pos], tans + mget[pos]);
}
int main() {
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  dfs(1, t, 0);
  cout << ans << endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

记忆化搜索的优缺点

优点：

• 记忆化搜索可以避免搜到无用状态，特别是在有状态压缩时
• 不需要注意转移顺序（这里的“转移顺序”指正常 dp 中 for 循环的嵌套顺序以及循环变量是递增还是递减）

举例：用常规 dp 写“合并石子”需要先枚举区间长度然后枚举起点，但记忆化搜索直接枚举断点（就是枚举当前区间由哪两个区间合并而成）然后递归下去就行

• 边界情况非常好处理，且能有效防止数组访问越界
• 有些 dp（如区间 dp) 用记忆化搜索写很简单但正常 dp 很难
• 记忆化搜索天生携带搜索天赋，可以使用技能“剪枝”！

缺点：

• 致命伤：不能滚动数组！
• 有些优化比较难加
• 由于递归，有时效率较低但不至于 TLE（状压 dp 除外）

记忆化搜索的注意事项

• 千万别忘了加记忆化！
• 边界条件要加在检查当前数组值是否为非法数值（防止越界）
• 数组不要开小了

背包 DP

0-1 背包

Jin Ge Jin Qu hao UVA - 12563 （劲歌金曲）01背包，求装入的东西最多（相同多时价值大）

意概要：有 n个物品和一个容量为 W 的背包，每个物品有重量$w_i$ 和价值$v_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

在上述例题中，由于每个物体只有2 种可能的状态（取与不取），正如二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」。

例题中已知条件有第 i个物品的重量 $w_i$，价值 $v_i$，以及背包的总容量W 。

设 DP 状态 $f_{i,j}$为在只能放前 i 个物品的情况下，容量为j 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 i-1个物品的所有状态，那么对于第 i个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为$f_{i-1,j}$ ；当其放入背包时，背包的剩余容量会减小$w_i$ ，背包中物品的总价值会增大$v_i$ ，故这种情况的最大价值为 $f_{i-1,j-w_i}+v_i$。
由此可以得出状态转移方程：
$f_{i,j}=max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$
这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。

由于对 $f_i$有影响的只有 $f_{i-1}$，可以去掉第一维，直接用 $f_i$ 来表示处理到当前物品时背包容量为 的最大价值，得出以下方程：$f_j=max(f_j,f_{j-w_i}+v_i)$
如果第二层循环正着遍历，对于当前处理的物品 i 和当前状态$f_{i,j}$ ，在 $j\ge w_i$时， $f_{i,j}$是会被$f_{i,j-w-i}$ 所影响的。这就相当于物品i 可以多次被放入背包，与题意不符。（事实上，这正是完全背包问题的解法）

为了避免这种情况发生，我们可以改变枚举的顺序，从W 枚举到$w_i$ ，这样就不会出现上述的错误，因为$f_{i,j}$ 总是在$f_{i,j-w_i}$ 前被更新。

核心代码：

for (int i = 1; i <= n; i++)
  for (int l = W; l >= w[i]; l--) 
  f[l] = max(f[l], f[l - w[i]] + v[i])
1
2
3

完全背包

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。
Piggy-Bank POJ - 1384（完全背包+背包放满）

二维费用背包

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间）。这种问题其实很简单：方程基本不用变，只需再开一维数组，同时转移两个价值就行了！（完全、多重背包同理）
这时候就要注意，再开一维存放物品编号就不合适了，因为容易 MLE。

for (int k = 1; k <= n; k++) {
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);
}
1
2
3
4
5

分组背包

所谓分组背包，就是将物品分组，每组的物品相互冲突，最多只能选一个物品放进去。
这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。
再说一说如何进行存储。我们可以将$t_{k,i}$ 表示第 k组的第i 件物品的编号是多少，再用 $cn{t}_k$ 表示第k 组物品有多少个。

for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])
        dp[i] = max(dp[i],dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移
1
2
3
4
5

输出方案

输出方案其实就是记录下来背包中的某一个状态是怎么推出来的。我们可以用$g_{i,v}$ 表示第 i 件物品占用空间为 v的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略（选或不选）。输出时的伪代码：

int v = V;  // 记录当前的存储空间
for (
    从最后一件循环至第一件)  // 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
{
  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}
1
2
3
4
5
6
7
8
9
10

求方案数

对于给定的一个背包容量、物品费用、其他关系等的问题，求装到一定容量的方案总数。
这种问题就是把求最大值换成求和即可。
例如 0-1 背包问题的转移方程就变成了：
$d{p}_i=\Sigma (d{p}_i,d{p}_{i-c_i})$
初始条件：$d{p}_0=1$
因为当容量为 0 时也有一个方案：什么都不装！

求最优方案总数

for (int i = 0; i < N; i++) {
  for (int j = V; j >= v[i]; j--) {
    int tmp = max(dp[j], dp[j - v[i]] + w[i]);
    int c = 0;
    if (tmp == dp[j]) c += cnt[j];                       // 如果从dp[j]转移
    if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]];  // 如果从dp[j-v[i]]转移
    dp[j] = tmp;
    cnt[j] = c;
  }
}
int max = 0;  // 寻找最优解
for (int i = 0; i <= V; i++) {
  max = max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] == max) {
    res += cnt[i];  // 求和最优解方案数
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

区间 DP

Click Here

DAG 上的 DP

树形 DP

Click Here

状压 DP

Click Here

数位 DP

(1)Round Numbers POJ - 3252（数位dp+判断前导零）
(2)数位dp总结 之 从入门到模板（stO）

插头 DP

计数 DP

Sumsets POJ - 2229（计数dp）

动态 DP

概率 DP

Click Here

DP 优化

单调队列/单调栈优化

斜率优化

四边形不等式优化

状态设计优化

其它 DP 方法