算法备忘录·动态规划

本文最后更新于:2022年2月23日 上午

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

动态规划

闫氏 DP 分析法

背包问题

01 背包问题

  • 问题:nn 个物品,每个物品的体积是 viv_i,价值是 wiw_i,背包的容量是 mm。若每个物品最多只能装一个,且不能超过背包容量,则背包的最大价值是多少?
  • DP 分析
- 模板 - 二维形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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];
  • 利用滚动数组的原理转化为一维形式
1
2
3
4
5
6
7
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];

完全背包问题

  • 问题:nn 个物品,每个物品的体积是 viv_i,价值是 wiw_i,背包的容量是 mm。若每个物品有任意多个,且不能超过背包容量,则背包的最大价值是多少?
  • DP 分析(优化后)
- 模板 - 未优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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];
  • 优化后(公式推出)
1
2
3
4
5
6
7
8
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 背包,也能转换为一维形式
1
2
3
4
5
6
7
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]

多重背包问题

  • 问题:nn 个物品,每个物品的体积是 viv_i,价值是 wiw_i,背包的容量是 mm。若每个物品至多装 sis_i,且不能超过背包容量,则背包的最大价值是多少?
  • 思路:多重背包问题不能像完全背包问题那样基于公式优化。它的优化思路是二进制优化——对于有 sis_i 件的物品 ii,可以打包为 [logsi][\log s_i] 个物品,每包有 1,2,4,,2k,C1,2,4,\cdots,2^k,C 件物品 ii',其中 k=[logsi]1k = [\log s_i] - 1。这样,就转换为了 01 背包问题。
    • 时间复杂度 O(nmlogs)O(nm\log s)
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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];

分组背包问题

  • 问题:nn 个物品,每个物品的体积是 viv_i,价值是 wiw_i,背包的容量是 mm。若每物品最多只能装一个,且不能超过背包容量,则背包的最大价值是多少?
  • 思路:带有约束的 01 背包问题,递推方程 f(i,j)=max{f(i1,j),f(i1,jv(i,k))+w(i,k)}f(i, j) = max\left\{f(i - 1, j), f(i - 1, j - v(i, k)) + w(i, k)\right\}
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 分析:
- 贪心优化: - 二分版:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 版
1
2
3
4
5
6
7
8
9
10
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
1
2
3
4
5
6
7
8
9
10
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

整数划分

  • 问题:把 nn 拆分成 1n1\sim n 的和的方案数(不考虑顺序)
  • DP 分析:
    • 基于完全背包问题
    - 基于“总和-个数”

数位统计 DP

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

计算问题

  • 问题:给定两个整数 aabb,求 aabb 之间的所有数字中 090\sim 9的出现次数
  • 思路:实现 count(n,x),表示 1n1\sim n 中,数字 xx 出现的次数。
    • 考虑 xxn=abcdefgn=abcdefg 第四位 dd 时出现的次数。可以将 nn 看成 yyyxzzzyyyxzzz
      • 000yyy(abc1)000\leq yyy \leq (abc - 1) 时,000zzz999000\leq zzz \leq 999
        • x0x\neq 0,此时 xx 出现了 abc×1000abc\times 1000
        • x=0x= 0,由于 000000nn 实际并没有第四位 xx,所以此时 xx 共出现了 (abc1)×1000(abc - 1)\times 1000
      • yyy=abcyyy=abc 时:
        • d<xd < xabcdefg<abcdefgabcdefg < abcdefg,此时 xx 出现 0 次;
        • d=xd = x000zzzefg000\leq zzz \leq efg,此时 xx 出现 efg+1efg+1
        • d>xd > x000zzz999000\leq zzz \leq 999,此时 xx 出现 10001000

状态压缩 DP

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

蒙德里安的梦想

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

最短 Hamilton 路径

  • T:91. 最短 Hamilton 路径
  • DP 分析:

树形 DP

  • 树形 DP:在树上进行的 DP

没有上司的舞会

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

记忆化搜索

  • 任何一个 DP 方程都能转为记忆化搜索。记忆化搜索的优点是特别好写,但是效率有时不如 DP 写法
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int g[MAXN];

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

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

滑雪

  • T:901. 滑雪
  • DP 分析:

算法备忘录系列目录:
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·STL
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析


算法备忘录·动态规划
https://justloseit.top/算法备忘录·动态规划/
作者
Joker
发布于
2022年2月4日
许可协议