算法备忘录·动态规划

本文最后更新于 2022年11月22日中午

一直以来，没能系统学习算法，是我心中的痛；现在学了 y 总的算法基础课，做做笔记，希望能够有所收获。
这是第六节，动态规划。

动态规划

闫氏 DP 分析法

背包问题

01 背包问题

问题： $n$ 个物品，每个物品的体积是 $v_i$ ，价值是 $w_i$ ，背包的容量是 $m$ 。若每个物品最多只能装一个，且不能超过背包容量，则背包的最大价值是多少？
DP 分析

- 模板 - 二维形式

int n;  // 物品总数
int m;  // 背包容量
int v[N];  // 重量
int w[N];  // 价值

int f[N][M];  // f[i][j] 表示 在考虑前 i 个物品后，背包容量为 j 条件下的 max 价值
for (int i = 1; i <= n; i ++ )// 从 1 开始是因为 i 为 0 时，f 一定为 0
    for (int j = 1; j <= m; j ++ )
        if (j < v[i])  f[i][j] = f[i - 1][j];  // 当前重量装不进
        else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

cout << f[n][m];

利用滚动数组的原理转化为一维形式

int f、[M];
for (int i = 1; i <= n; i ++ )
    for (int j = m; j >= v[i]; j --  )  // 注意是倒序
        f[i][j] = max(f[j], f[j - v[i]] + w[i]);
    

cout << f[m];

完全背包问题

问题： $n$ 个物品，每个物品的体积是 $v_i$ ，价值是 $w_i$ ，背包的容量是 $m$ 。若每个物品有任意多个，且不能超过背包容量，则背包的最大价值是多少？
DP 分析（优化后）

- 模板 - 未优化

  int n;  // 物品总数
  int m;  // 背包容量
  int v[N];  // 重量
  int w[N];  // 价值

  int f[N][M];
  for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= m; j ++ )
         for (int k = 0; k *v[i] <= j; k ++ )
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k* w[i]);

  cout << f[n][m];

优化后（公式推出）

int f[N][M];
for (int i = 1; i <= n; i ++ )
    for(int j = 1; j <= m; j ++ )
        if (j < v[i]) f[i][j] = f[j - 1][j];
        else f[i][j] = max(f[i -1][j], f[i][j - v[i]] + w[i]);  // 注意！这里和 01 背包的脚标有区别


cout << f[n][m]

类似于 01 背包，也能转换为一维形式

int f[M];
for (int i = 1; i <= n; i ++ )
    for(int j = v[i]; j <= m; j ++ )
         f[j] = max(f[j], f[j - v[i]] + w[i]);  // 仍然是正序！


cout << f[m]

多重背包问题

问题： $n$ 个物品，每个物品的体积是 $v_i$ ，价值是 $w_i$ ，背包的容量是 $m$ 。若每个物品至多装 $s_i$ 个，且不能超过背包容量，则背包的最大价值是多少？
思路：多重背包问题不能像完全背包问题那样基于公式优化。它的优化思路是二进制优化——对于有 $s_i$ $s_{i}$ 件的物品 $i$ $i$ ，可以打包为 $[\log s_i]$ $[lo g s_{i}]$ 个物品，每包有 $1,2,4,\cdots,2^k,C$ $1, 2, 4, \dots, 2^{k}, C$ 件物品 $i'$ $i^{'}$ ，其中 $k = [\log s_i] - 1$ $k = [lo g s_{i}] - 1$ 。这样，就转换为了 01 背包问题。
- 时间复杂度 $O(nm\log s)$
模板

int n;  // 物品总数
int m;  // 背包容量
int v[N];  // 重量 
int w[N];  // 价值


// 读入物品个数时重新打包
int a, b, s;
cin >> a >> b >> s;  //  该物品的重量、价值、最大数量
int k = 1;  // 当前包裹大小
while (k <= s){
    cnt ++;  // 实际物品种数
    v[cnt] = a * k;
    w[cnt] = b * k;
    s -= k;
    k *= 2;
}

if (s > 0){ // 不足的补足到大小为 C 的包裹
    cnt ++;
    v[cnt] = a * s;
    w[cnt] = b * s;
}


n = cnt;  // 更新物品种数


// 01 背包问题
for (int i = 1; i <= n; i ++ )
    for (int j = m; j >= v[i]; j -- )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m];

分组背包问题

问题： $n$ 个物品，每个物品的体积是 $v_i$ ，价值是 $w_i$ ，背包的容量是 $m$ 。若每组物品最多只能装一个，且不能超过背包容量，则背包的最大价值是多少？
思路：带有约束的 01 背包问题，递推方程 $f(i, j) = max\left\{f(i - 1, j), f(i - 1, j - v(i, k)) + w(i, k)\right\}$
模板

int n;  // 物品总数
int m;  //背包容量
int v[N][S];  // 重量
int w[N][S];  // 价值
int s[N];  // 各组物品种数


// 读入数据
for (int i = 1; i <= n; i ++ ){
    cin >> s[i];
    for (int j = 1; j <= s[i]; j ++ )
        cin >> v[i][j] >> w[i][j];
}


for (int i = 1; i <= n; i ++ )
    for (int j = m; j >= 1; j -- )
        for (int k = 1; k <= s[i]; k ++ )
            if (v[i][k] < j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);


cout << f[m];

线性 DP

线性 DP：状态之间有线性关系的动态规划问题
没有比较固定的模板

数字三角形

T：898. 数字三角形
DP 分析：

最长上升子序列

T：895. 最长上升子序列
DP 分析：

- 贪心优化： - 二分版：

int len = 0;  // 最长上升子序列 q[] 长度
for (int i = 0; i < n; i ++ )
  {
      int l = 0, r = len;
      while (l < r)
      {
          int mid = l + (r - l) / 2;
          if (q[mid] < a[i]) l = mid;
          else r = mid + 1;
      }
      q[r ++ ] = a[i];
      len = max(len, r);
  }
cout << len << endl;

stl 版

vector<int> stk;            //类似于单调栈
stk.push_back(arr[0]);

for (int i = 1; i < n; i ++ ) {
    if (arr[i] > stk.back())        
        stk.push_back(arr[i]);          // 如果该元素大于栈顶元素,将该元素入栈
    else
        *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];  // 替换掉第一个大于或者等于这个数字的那个数
}
cout << stk.size() << endl;

最长公共子序列

T：897. 最长公共子序列
DP 分析：

最短编辑距离

T：902. 最短编辑距离
DP 分析：

区间 DP

线性 DP 的扩展，以区间长度为阶段，使用能足够表示区间的坐标表示状态
特点：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
模板
- 所有的区间 DP 问题，第一维都是枚举区间长度，一般 len = 1 用来初始化，枚举从 len = 2 开始，第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

for (int i = 1; i <= n; i++) {
    dp[i][i] = default_value;
}
for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程
            // ...
        }
    }

石子合并

T：282. 石子合并
DP 分析：

计数类 DP

整数划分

问题：把 $n$ 拆分成 $1\sim n$ 的和的方案数（不考虑顺序）
DP 分析：
- 基于完全背包问题
- 基于“总和-个数”

数位统计 DP

数位：把一个数字按照个、十、百、千等等逐位拆开，关注它每一位上的数字。
数位 DP 的基本原理：对于位数比较多的数，这样的过程中有许多重复的部分。我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
- 数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（类似于前缀和）

计算问题

问题：给定两个整数 $a$ 和 $b$ ，求 $a$ 和 $b$ 之间的所有数字中 $0\sim 9$ 的出现次数
思路：实现 count(n,x)，表示 $1\sim n$ $1 \sim n$ 中，数字 $x$ $x$ 出现的次数。
- 考虑 $x$ $x$ 在 $n=abcdefg$ $n = a b c d e f g$ 第四位 $d$ $d$ 时出现的次数。可以将 $n$ $n$ 看成 $yyyxzzz$ $y y y x z z z$
  - 当 $000\leq yyy \leq (abc - 1)$ $000 \leq y y y \leq (a b c - 1)$ 时， $000\leq zzz \leq 999$ $000 \leq z z z \leq 999$ ：
    - 当 $x\neq 0$ ，此时 $x$ 出现了 $abc\times 1000$ 次
    - 当 $x= 0$ ，由于 $000$ 时 $n$ 实际并没有第四位 $x$ ，所以此时 $x$ 共出现了 $(abc - 1)\times 1000$ 次
  - 当 $yyy=abc$ $y y y = a b c$ 时：
    - 当 $d < x$ ， $abcdefg < abcdefg$ ，此时 $x$ 出现 0 次；
    - 当 $d = x$ ， $000\leq zzz \leq efg$ ，此时 $x$ 出现 $efg+1$ 次
    - 当 $d > x$ ， $000\leq zzz \leq 999$ ，此时 $x$ 出现 $1000$ 次

状态压缩 DP

状态压缩是通过用二进制数表示状态实现的

蒙德里安的梦想

T：291. 蒙德里安的梦想
DP 分析：

最短 Hamilton 路径

T：91. 最短 Hamilton 路径
DP 分析：

树形 DP

树形 DP：在树上进行的 DP

没有上司的舞会

T：285. 没有上司的舞会
DP 分析：

记忆化搜索

任何一个 DP 方程都能转为记忆化搜索。记忆化搜索的优点是特别好写，但是效率有时不如 DP 写法
模板

int g[MAXN];

int f(状态参数) {
  if (g[规模] != 无效数值) return g[规模];
  if (终止条件) return 最小子问题解;
  g[规模] = f(缩小规模);
  return g[规模];
}

int main() {
  // ...
  memset(g, 无效数值, sizeof(g));
  // ...
}