常见问题
闫式DP分析法
- 状态表示
- 集合
- 满足一定条件的所有方案
- 属性
- 集合（所有方案）的某种属性（Max、Min、Count等）
- 集合
- 状态计算（集合划分）
- 如何将当前集合划分成多个子集合
状态计算相当于集合的划分：把当前集合划分成若干个子集，使得每个子集的状态可以先算出来，从而推导当前集合状态（曲线救国）
集合划分规则：不重，不漏
特殊情况：属性是 MAX、MIN 的时候，划分的集合是可以重复的
举个例子 A、B、C，先求A、B的最大值，然后求B、C的最大值，最后求两个最大值的最大值，依旧是A、B、C的最大值。例题 ⭐ 897 最长公共子序列
时间复杂度
状态表示数量 * 状态计算量（转移计算量）
如完全背包问题，假定 N 件物品，物品最低体积为 1，背包最大体积容量 V
朴素二维情况：状态表示数量就是 (NV)，状态计算量就是物品体积为 1 的时候（最坏情况），最内层循环最多需计算 V 次，时间复杂度(O(NV^2))
状态转移路径
DP本质是在一个拓扑图内找最短路
每个状态(f(i,j))看作一个点，状态的转移看作一条边，把状态的值理解为最短路径长
更新最短路的规则是根据题目来的，如完全背包规则 (f(i,j)=Max(f(i-1,j-k*v[i])+k*w[i]))
DP结束最终会把从 初始状态（起点）到 目标状态 （终点）的 最短路径长 更新出来（生成了一颗最短路径树）
那么 DP求状态转移路径 就变成了在 拓扑图 中找 最短路径 的问题了，沿用 最短路 输出路径的方法就可以找出 状态的转移
方案总结：循环 与 dfs 均可实现
- 逆推：获取最终状态，根据 最短路规则 逆序往前推，直到 起始状态 ，逐一输出每个状态
- 边转移边记录：状态转移过程中，记录每一条边，再利用递推的栈机制，后序输出
注意的点：
- 因为需要记录路径，状态转移方程可能不好被维度优化，具体问题具体分析
- 边转移边记录一般需要开一个与状态表示一致维度的数组，要存储每个状态是从上一层哪一状态转移过来的；而逆推不需要一致，具体可看下题（保存每组从前组的哪个状态转移过来，一维）
来看一道分组背包题1013 机器分配，要求输出每组选择了哪个物品，我给的题解是第一种方案的循环版本
从终点状态逆推，必定有一条边满足最短路规则，记录当前边，并减去当前组物品的体积，接着开始推前一组状态，直到起始状态
int j = m; for (int i = n; i; i--) { for (int k = 0; k <= j; k++) { if (f[i][j] == f[i - 1][j - k] + w[i][k]) { path[i] = k; j -= k; break; } } }
可改写成 dfs 的版本
void dfs(int i, int j) { if (!i) return; for (int k = 0; k <= j; k++) { if (f[i - 1][j - k] + w[i][k] == f[i][j]) { path[cnt++] = k; dfs(i - 1, j - k); return; } } }
也可用第二种方案，边转移边记录（辅助下标 cnt 就不需要了）
for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) { for (int k = 0; k <= j; k++) { int temp = max(f[i][j], f[i - 1][j - k] + w[i][k]); if (temp == f[i - 1][j - k] + w[i][k]) path[i][j] = max(path[i][j], k); f[i][j] = temp; } } cout << f[n][m] << endl; 输出既可以循环输出（倒着输出），也可以 dfs 逆序输出（正着输出）
void dfs(int i, int j) { if (!i) return; int k = path[i][j]; dfs(i - 1, j - k); cout << i << " " << k << endl; } int j = m; for (int i = n; i >= 1; i--) { cout << i << " " << path[i][j] << endl; j -= path[i][j]; }
背包问题初始化
变量声明
一定要根据状态表示的含义，来声明所需变量
如分组背包题 1013 机器分配，最多 10 组，每组 15 个物品，那么定义的常数 N、M 分别表示状态中每维的最大数量（多申请一点）
path 数组用于边转移边记录路径，理所应当和 f 数组是一致维度的大小；写成 path[N][N] 一直找不出问题的屑。
状态初始化
本篇内容只涉及了 至多、恰好 两种情况的问，至少 情况将在提高篇提及
关于 f[0] = 1 的解释，请看 278 01背包 计数
求方案数 二维情况 1、体积至多j，f[0][i] = 1, 0 <= i <= m，其余是0 2、体积恰好j，f[0][0] = 1, 其余是0 一维情况 1、体积至多j，f[i] = 1, 0 <= i <= m， 2、体积恰好j，f[0] = 1, 其余是0 求最大值最小值 二维情况 1、体积至多j，f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只有求最大值题型） 2、体积恰好j， 求最小值：f[0][0] = 0, 其余是INF 求最大值：f[0][0] = 0, 其余是-INF 一维情况 1、体积至多j，f[i] = 0, 0 <= i <= m（只有求最大值题型） 2、体积恰好j， 求最小值：f[0] = 0, 其余是INF 求最大值：f[0] = 0, 其余是-INF
下标从1开始
如果状态转移涉及 (i-1) 层，DP问题下标最好从1开始（如第一个物品的下标是1），这是经验，基本上所有DP题目都是这样
递归
所有DP问题都可以改用递归，如 285 没有上司的舞会 901 滑雪
背包DP
01背包
(N) 个物品，(V_i) 表示体积，(W_i) 表示价值，每件物品只有一个。求背包装得下的情况下的最大价值多少
- 状态表示 (f(i,j))
- 集合
- 只考虑前 (i) 个物品，且总体积不大于 (j) 的所有选法
- 属性
- (max) （每个选法的总价值的最大值）
- 集合
- 状态计算
- 不含 (i) 的选法 集合，相当于 (f(i-1,j))
- 含 (i) 的选法 集合，相当于 (f(i-1,j-V_i) + W_i)
- 由于所有选法都包含第 (i) 物品，所以先把第 (i) 物品去掉，然后求最大值，然后再把第 (i) 物品加上
- 可能是空集 (j < V_i)，朴素代码中需要做判断
- 转移方程 (f(i,j) = max(f(i-1,j),f(i-1,j-V_i) + W_i))，满足 (V_i <= j)
朴素、二维
#include <algorithm> #include <iostream> using namespace std; int const N = 1e3 + 10; int n, m; int v[N], w[N]; int f[N][N]; // f[0][0~m] 默认都是0；1件物品都没选 int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // 把下面两行代码合并到一起看 f[i][j] = f[i - 1][j]; if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } } cout << f[n][m] << endl; return 0; } 优化、一维
- (f(i))只用到了(f(i-1))这一层，可以用滚动数组来做
- 把 (j) 当做一维数组下标位置，如果从小到大枚举体积，会覆盖上一层数据，因此从大到小枚举体积，另外可以限制 (j) 遍历到 (v[i]) 停止，这样省了判断语句
#include <algorithm> #include <iostream> using namespace std; int const N = 1e3 + 10; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; 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] << endl; return 0; }
完全背包
(N) 个物品，(V_i) 表示体积，(W_i) 表示价值，每件物品无限多个。求背包装得下的情况下的物品最大价值多少
- 状态表示 (f(i,j))
- 集合
- 只考虑前 (i) 个物品，且总体积不大于 (j) 的所有选法
- 属性
- (max) （每个选法的总价值的最大值）
- 集合
- 状态计算
- 按第 (i) 个物品选多少个划分
- 0个：(f(i-1,j))
- k个：(f(i-1,j-k*v[i])+k*w[i])
- 去掉 (k) 个物品 (i) 的体积
- 求 (f(i-1,j-k*v[i]))
- 加上 (k) 个物品 (i) 的价值
- 转移方程 (f(i,j)=f(i-1,j-k*v[i])+k*w[i]) ，满足 (k*v[i]<=j)
朴素、二维
#include <algorithm> #include <iostream> using namespace std; const int N = 1e3 + 10; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i++) for (int j = 0; 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] << endl; return 0; }
优化、二维
#include <algorithm> #include <iostream> using namespace std; const int N = 1e3 + 10; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) { f[i][j] = f[i - 1][j]; if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; } 优化、一维
01背包、完全背包有相似之处
#include <algorithm> #include <iostream> using namespace std; const int N = 1e3 + 10; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; 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] << endl; return 0; }
优化重点
01背包和完全背包一维优化的不同点在状态转移方程上
- 如果用上一层状态就要从大到小枚举体积（01背包二维转一维）
- 如果用本层状态就要从小到大枚举体积（完全背包二维转一维）
多重背包
(N) 个物品，(V_i) 表示体积，(W_i) 表示价值，每件物品(X_i)个。求背包装得下的情况下的物品最大价值多少
- 状态表示 (f(i,j))
- 集合
- 只考虑前 (i) 个物品，且总体积不大于 (j) 的所有选法
- 属性
- (max) （每个选法的总价值的最大值）
- 集合
- 状态计算
- 转移方程 (f(i,j) = max(f(i-1,j-v[i] * k)+w[i]*k),kin[0,X_i])，满足 (k*v[i]<=j)
朴素、二维
#include <algorithm> #include <iostream> using namespace std; int const N = 1e2 + 10; int n, m; int v[N], w[N], x[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> x[i]; for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k <= x[i] && 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]; return 0; }
优化、一维⭐
二进制法，将 (X_i) 拆分成 (lceil log_2X_i rceil) 个物品（(1,2,4,8,16,...,2^k,C)），将多重背包转变成01背包问题
#include <algorithm> #include <iostream> using namespace std; int const N = 1000 * 11 + 10; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; int cnt = 0; for (int i = 1; i <= n; i++) { int a, b, x; cin >> a >> b >> x; int k = 1; while (k <= x) { cnt++; v[cnt] = a * k; w[cnt] = b * k; x -= k; k *= 2; } if (x > 0) { // 若 x 还有剩余 cnt++; v[cnt] = a * x; w[cnt] = b * x; } } n = cnt; 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] << endl; return 0; }
究极、单调队列⭐
分析问题
(begin{array}{l} 0<N leq 1000 \ 0<V leq 20000 \ 0<v_{i}, w_{i}, s_{i} leq 20000 end{array})
这种情况下，采用转01背包法，时间复杂度是 (1000 * log_220000*20000) = 1.4e4 + 2e4 = 3e8，肯定会TLE
单调队列
先认识一下单调队列是什么 C++算法之旅、05 基础篇 | 第二章 数据结构 - 小能日记
https://leetcode.cn/problems/sliding-window-maximum
#include <algorithm> #include <cstring> #include <iostream> #include <vector> using namespace std; class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res; int q[nums.size()]; memset(q, 0, sizeof q); int hh = 0, tt = -1; for (int i = 0; i < nums.size(); i++) { while (hh <= tt && q[hh] < i - k + 1) hh++; while (hh <= tt && nums[q[tt]] <= nums[i]) tt--; q[++tt] = i; // 插入位置 if (i + 1 >= k) res.push_back(nums[q[hh]]); } return res; } };
解决问题
先来看多重背包的朴素二维代码
for (int i = 1; i <= n; i++) for (int j = 0; j <= vt; j++) for (int k = 0; k <= s[i] && k * v[i] <= j; k++) { f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); } 可以这样优化，遍历每个物品，然后总体积 (j) 分为 (r) 类 （(r = v[i] - 1)）。选择其中一类，如第 (r) 类，那么从 (r) 遍历到 (vt) 的过程，即 int j = r; j <= vt; j += v[i] 这一过程，由于物品数量是有限的，相当于维护了一个固定宽度的滑动窗口，(j) 每移动一次，对滑动窗口做出滑动、删除、插入、选择四个操作，滑动窗口用单调队列实现，每个物体只需遍历一遍([0,vt])，原先的 (k) 循环被优化掉了，时间复杂度变为 (O(NV))
- 求 (w[i]) 个数，即队内元素 (j') 与当前 (j) 的差值 除以 (v[i])；也意味着选择了几个 (i) 物品
- 滑动：队头元素是否出界；也就是 (w[i]) 的个数 > (s[i]) ，选择了大于 (s[i]) 个物品
- 删除：维持单调队列特性；判断队尾每个 (j') 对应的属性值是否 <= (j) 当前对应的属性值，True就删除
- 对应的值计算公式
f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i]
- 对应的值计算公式
- 插入：将当前 (j) 插入队尾
- 选择：从队头取出 (j') ，对应的属性值就是 (f(i,j)) 的最大值（滑动窗口 (s[i]) 项里面选择最大一项）
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 1e3 + 10, M = 2e4 + 10; int n, vt; int v[N], w[N], s[N]; int f[N][M]; int q[M]; int main() { cin.tie(0); cin >> n >> vt; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i]; for (int i = 1; i <= n; i++) { for (int r = 0; r < v[i]; r++) { int hh = 0, tt = -1; for (int j = r; j <= vt; j += v[i]) { // 滑动 if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh++; // 删除 while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) tt--; // 插入 q[++tt] = j; // 选择 f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i]; } } } cout << f[n][vt]; return 0; }
优化代码①
循环已经减少了一层，但空间依旧需要(O(NV))，学着01背包优化的思路，用滚动数组优化一下代码，由于滑动的方向不可变，不能修改 for 循环里的 j，可以将相邻两层状态保存到 f 数组中 f[2][M]
- (i - 1) & 1 就是上一层
- i & 1 就是当前层
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 1e3 + 10, M = 2e4 + 10; int n, vt; int v[N], w[N], s[N]; int f[2][M]; int q[M]; int main() { cin.tie(0); cin >> n >> vt; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i]; for (int i = 1; i <= n; i++) { for (int r = 0; r < v[i]; r++) { int hh = 0, tt = -1; for (int j = r; j <= vt; j += v[i]) { // 滑动 if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh++; // 删除 while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) tt--; // 插入 q[++tt] = j; // 选择 f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i]; } } } cout << f[n & 1][vt]; return 0; }
优化代码②
不用滚动数组也可以，声明一个跟 f[M] 同等大小的数组 backup[M]，用于保存上一个物品 i 的所有状态。新一层循环每次都把上一层循环的 f 数组拷贝到 backup 数组中，这样新一层 i 就可以用到上一层 i 的状态了
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 1e3 + 10, M = 2e4 + 10; int n, vt; int v[N], w[N], s[N]; int f[M], backup[M]; int q[M]; int main() { cin.tie(0); cin >> n >> vt; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i]; for (int i = 1; i <= n; i++) { memcpy(backup, f, sizeof f); for (int r = 0; r < v[i]; r++) { int hh = 0, tt = -1; for (int j = r; j <= vt; j += v[i]) { // 滑动 if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh++; // 删除 while (hh <= tt && backup[q[tt]] + (j - q[tt]) / v[i] * w[i] <= backup[j]) tt--; // 插入 q[++tt] = j; // 选择 f[j] = backup[q[hh]] + (j - q[hh]) / v[i] * w[i]; } } } cout << f[vt]; return 0;
分组背包
(N) 个分组，每个分组里有(X)个物品，(V_i) 表示体积，(W_i) 表示价值，每组物品里选一个。求背包装得下的情况下的物品最大价值多少
- 状态表示 (f(i,j))
- 集合
- 只考虑前 (i) 组物品，且总体积不大于 (j) 的所有选法
- 属性
- (max) （每个选法的总价值的最大值）
- 集合
- 状态计算
- 不选第 i 组物品、选第 i 组第 1 个物品、选第 i 组第 2 个物品、...选第 i 组最后一个物品
- 不选第 i 组物品：(f(i-1,j))
- 选第 i 组物品第 k 个物品：(f(i-1,j-v[i,k])+w[i,k])
- 可能是空集 (j < V_{ik}) ，朴素代码中需要做判断
- 转移方程 (f(i,j) = max(f(i-1,j),f(i-1,j-v[i,k])+w[i,k]),kin [1,X_i])，满足 (v[i,k]<=j)
朴素、二维
#include <algorithm> #include <iostream> using namespace std; int const N = 1e2 + 10; int n, m; int v[N][N], w[N][N], x[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> x[i]; // 这里与上面状态转移方程不同，下标从0开始，个人喜好 for (int j = 0; j < x[i]; j++) { cin >> v[i][j] >> w[i][j]; } } for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) { f[i][j] = f[i - 1][j]; for (int k = 0; k < x[i]; k++) if (v[i][k] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]); } cout << f[n][m]; return 0; }
优化、一维
#include <algorithm> #include <iostream> using namespace std; int const N = 1e2 + 10; int n, m; int v[N][N], w[N][N], x[N]; int f[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> x[i]; for (int j = 0; j < x[i]; j++) { cin >> v[i][j] >> w[i][j]; } } for (int i = 1; i <= n; i++) for (int j = m; j >= 0; j--) for (int k = 0; k < x[i]; k++) if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); cout << f[m]; return 0; }
混合背包
物品分类
判断当前物品是哪个类的，然后转移的时候按照各个类的逻辑去转移。本题中的多重背包还可以拆分成 01 背包，所以只需要判断两个类
#include <algorithm> #include <cstring> #include <iostream> #include <vector> using namespace std; int const N = 1e3 + 10; int n, vt; int f[N]; struct Thing { int kind; int v, w; }; vector<Thing> things; int main() { cin >> n >> vt; // 分类 for (int i = 0; i < n; i++) { int v, w, s; cin >> v >> w >> s; if (s < 0) things.push_back({-1, v, w}); else if (s == 0) things.push_back({0, v, w}); else { for (int k = 1; k <= s; k *= 2) { s -= k; things.push_back({-1, v * k, w * k}); } if (s > 0) things.push_back({-1, v * s, w * s}); } } for (auto thing : things) { if (thing.kind < 0) { for (int j = vt; j >= thing.v; j--) { f[j] = max(f[j], f[j - thing.v] + thing.w); } } else if (thing.kind == 0) { for (int j = thing.v; j <= vt; j++) { f[j] = max(f[j], f[j - thing.v] + thing.w); } } } cout << f[vt] << endl; return 0; }
二维费用
体积重量
涉及到了体积与重量，将原先01背包优化后的 (f(i)) 变成 (f(i,j))
- (f(i)) 总体积不超过 (i) 的最大价值
- (f(i,j)) 总体积不超过 (i) 且总重量不超过 (j) 的最大价值
时间复杂度 (O(NVM))；因为要用到上一层状态，所以是 (i,j) 都是从大到小枚举；读入物品信息和更新一层状态可以放在一起进行
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 110; int n, m, v; int f[N][N]; int main() { cin >> n >> v >> m; for (int i = 0; i < n; i++) { int vx, mx, wx; cin >> vx >> mx >> wx; for (int j = v; j >= vx; j--) { for (int k = m; k >= mx; k--) { f[j][k] = max(f[j][k], f[j - vx][k - mx] + wx); } } } cout << f[v][m]; return 0; }
方案计数⭐
朴素、二维
- 状态表示 (g(i,j))
- 集合
- 考虑前 (i) 件物品，总体积恰好为 (j)，且总价值最大的所有选法
- 属性
- (count)
- 集合
- 状态计算
- 选 i 的价值的是最大的
- (g(i,j)=g(i-1,j-v))
- 不选 i 的价值是最大的
- (g(i,j)=g(i-1,j))
- 选 i 和不选 i 的价值都是最大的
- (g(i,j)=g(i-1,j-v)+g(i-1,j))
- 选 i 的价值的是最大的
如何判断状态计算的三种情况：根据已更新完的 (f(i,j)) 来判断，举个例子，如果 (f(i,j)) 从 (f(i-1,j)) 转移过来，那可能就是（不选 i ，选 i 和不选 i ）这两种情况，接着判断就行
g 数组更新完后需要遍历最后一层与最大总价值(f(i,j))相同的各项：即考虑前 i 个物品，总体积恰好为 ([0,j]) 的最大总价值的方案数的和
#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 1e3 + 10; int v[N], w[N]; int f[N][N]; int g[N][N]; int n, vt; int mod = 1e9 + 7; int main() { cin >> n >> vt; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= n; i++) { for (int j = 0; j <= vt; j++) { f[i][j] = f[i - 1][j]; if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } } g[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= vt; j++) { if (f[i][j] == f[i - 1][j]) g[i][j] = (g[i][j] + g[i - 1][j]) % mod; if (v[i] <= j && f[i][j] == f[i - 1][j - v[i]] + w[i]) g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mod; } } int res = 0; for (int j = 0; j <= vt; ++j) { if (f[n][j] == f[n][vt]) { res = (res + g[n][j]) % mod; } } cout << res << endl; return 0; }
优化、一维
可以发现 g 数组的更新都是根据 f 数组状态更新的路径来的，两个循环可以放在一块。同时可以用一维数组优化
#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 1e3 + 10; int v[N], w[N]; int f[N]; int g[N]; int n, vt; int mod = 1e9 + 7; int main() { cin >> n >> vt; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; g[0] = 1; for (int i = 1; i <= n; i++) { for (int j = vt; j >= v[i]; j--) { int temp = max(f[j], f[j - v[i]] + w[i]), c = 0; if (temp == f[j]) c = (c + g[j]) % mod; if (temp == f[j - v[i]] + w[i]) c = (c + g[j - v[i]]) % mod; f[j] = temp, g[j] = c; } } int res = 0; for (int j = 0; j <= vt; ++j) { if (f[j] == f[vt]) { res = (res + g[j]) % mod; } } cout << res << endl; return 0; }
方案记录
所有背包问题都可以把方案数出来，相当于求状态转移路径，本题的难点在于字典序输出
针对第一个物品选择有三种情况，后续物品也按这个思路考虑
- 只能选，必选
- 只能不选，必不选
- 可选可不选，必选（保证题目要求的字典序）
原来的背包DP是从 1 推到 n，从 n 逆推的时候并不能保证字典序，况且可能有多个物品选择方式（看看方案计数问题）
所以需要倒过来从 n 推到 1，此时 (f(1,m)) 就是最大总价值，就可以从 1 开始逆推了
#include <bits/stdc++.h> using namespace std; int const N = 1e3 + 10, V = 1e3 + 10; int n, vt; int v[N], w[N]; int f[N][V]; int path[N], cnt; int main() { cin >> n >> vt; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } for (int i = n; i >= 1; i--) { for (int j = 0; j <= vt; j++) { f[i][j] = f[i + 1][j]; if (v[i] <= j) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]); } } // f[1][m] 最大值 int j = vt; for (int i = 1; i <= n; i++) if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) { cout << i << ' '; j -= v[i]; } return 0; }
练习题
278 01背包 计数
- 状态表示 (f(i,j))
- 集合
- 考虑前 (i) 个物品，总体积恰好等于 (j) 的选法集合
- 属性
- (count)
- 集合
- 状态计算
- 不选第 i 物品的所有方案：(f(i-1,j))
- 选择第 i 物品的所有方案：(f(i-1,j-V_i))
- 转移方程：(f(i,j) = f(i-1,j) + f(i-1,j-V_i))
f[0] = 1 含义
f[0] = 1; 表示从前 0 个物品选出总体积为 0 的方案数为 1；一个物品都不选，此时总体积为0，这也是一种合法的方案
二维写法，即 (f(i,0) = 0 , i in [0,n])，表示从前 (i) 个物品选出总体积为 0 的方案数为 1
如计算转移的状态 (f(i-1,j-s*V_i)) 中，如果恰好 (j-s*V_i =0)，代表恰好 (s) 个 (i) 物品能够满足 (j) 的要求，此时是一种合法的方案
题解
#include <algorithm> #include <iostream> using namespace std; int const N = 1e2 + 10, M = 1e4 + 10; int n, m; int v[N]; int f[M]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i]; f[0] = 1; for (int i = 1; i <= n; i++) for (int j = m; j >= v[i]; j--) { f[j] = f[j] + f[j - v[i]]; } cout << f[m]; return 0; }
423 01背包 Max
(f(i,j))考虑前 (i) 个草药，采集时间不超过 (j) 的所有方案的最大总价值
#include <algorithm> #include <iostream> using namespace std; int const N = 1e2 + 10, M = 1e3 + 10; int n, m; int v[N], w[N]; int f[M]; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= m; i++) for (int j = n; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[n]; return 0; }
426 01背包 Max
(f(i,j)) 考虑前 (i) 个物品，在不超过 (j) 元的情况下，所有方案的价格重要度乘积和的最大值
#include <algorithm> #include <iostream> using namespace std; int const N = 1e2, M = 3e4 + 10; int n, m; int v[N], w[N]; int f[M]; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= m; i++) for (int j = n; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + v[i] * w[i]); cout << f[n]; return 0; }
279 完全背包 计数
- 状态表示 (f(i,j))
- 集合
- 只考虑前 (i) 个物品（每个物品若干个），且总体积恰好等于 (j) 的所有选法
- 属性
- (count)
- 集合
- 状态计算
- 不选：(f(i-1,j))
- 选第 (i) 个 (k) 件物品：(f(i-1,j-V_i*k))
- 转移方程 (f(i,j) = sum f(i-1,j-V_i*k)) 满足 (k*v[i]<=j)
以下是优化后的写法
#include <algorithm> #include <iostream> using namespace std; int const N = 4e3 + 10; int n; unsigned f[N]; int main() { cin >> n; // 初始化 f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { f[j] += f[j - i]; } } cout << (f[n] - 1) % 2147483648u << endl; return 0; }
587 完全背包 Min
- 状态表示 (f(i,j))
- 集合
- 考虑前 (i) 个物品，总体积恰好等于 (j) 的所有方案
- 属性
- (min) （每个方案的元素个数）
- 集合
- 状态计算
- 不选第 i 个：(f(i-1,j))
- 选第 i 个 k 件物品：(f(i-1,j-V_i*k) + k)
- 转移方程 (f(i,j) = min(f(i-1,j-V_i*k) + k))
- (f(0,0)) 为 0（什么都不选元素个数为0）；其他 (f(i,j)) 全部 INF（Min）；物品数量 (lfloor sqrt(N) rfloor)
朴素写法 （优化写法在后面）
状态数量 (nlog_2n) ，状态转移计算 (n) 次（实际比n小），时间复杂度 (O(n^2log_2n))，会TLE
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 1e2, M = 1e4 + 10; int t, n; int f[N][M]; int main() { cin >> t; for (int id = 1; id <= t; id++) { cin >> n; int m = 1; while (m * m <= n) m++; m--; // 初始化状态 memset(f, 0x3f, sizeof f); f[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k * (i * i) <= j; k++) { f[i][j] = min(f[i][j], f[i - 1][j - k * (i * i)] + k); } } } cout << "Case #" << id << ": " << f[m][n] << endl; } return 0; }
优化写法
for (int i = 1; i <= m; i++) { for (int j = 0; j <= n; j++) { f[i][j] = f[i - 1][j]; if (i * i <= j) f[i][j] = min(f[i][j], f[i][j - i * i] + 1); } } cout << "Case #" << id << ": " << f[m][n] << endl; }
一维写法
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 1e2, M = 1e4 + 10; int t, n; int f[M]; int main() { cin >> t; for (int id = 1; id <= t; id++) { cin >> n; memset(f, 0x3f, sizeof f); f[0] = 0; for (int i = 1; i <= n / i; i++) { for (int j = i * i; j <= n; j++) { f[j] = min(f[j], f[j - i * i] + 1); } } cout << "Case #" << id << ": " << f[n] << endl; } return 0; }
1013⭐分组背包
将每个公司当做物品组，如第一个公司（物品组）包括三个物体（分一台、分两台、分三台）
-
第 (i) 公司第 (k) 件物品
- 含义：分给第 (i) 个公司 (k) 台机器
- 体积：(k)
- 价值：(w_{ik})
-
状态表示 (f(i,j))
- 集合
- 只考虑前 (i) 组物品，且总体积不大于 (j) 的所有选法
- 属性
- (max) （每个选法的总价值的最大值）
- 集合
-
状态计算
- 不选第 i 组物品、选第 i 组第 1 个物品、选第 i 组第 2 个物品、...选第 i 组最后一个物品
- 不选第 i 组物品：(f(i-1,j))
- 选第 i 组物品第 k 个物品：(f(i-1,j-v[i,k])+w[i,k])
题目还要求输出每个公司选择了哪个物品，是求状态转移路径问题
#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 11, M = 16; int n, m; int w[N][M]; int f[N][M]; int way[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> w[i][j]; for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) { // f[i][j] = f[i - 1][j]; // 如果写了下面 k 改成 1 for (int k = 0; k <= j; k++) { f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]); } } cout << f[n][m] << endl; int j = m; for (int i = n; i; i--) { for (int k = 0; k <= j; k++) { if (f[i][j] == f[i - 1][j - k] + w[i][k]) { way[i] = k; j -= k; break; } } } for (int i = 1; i <= n; i++) cout << i << " " << way[i] << endl; return 0; }
线性DP
递推方程是线性关系（如背包问题二维矩阵，是一行一行来求的）
898 数字三角形
- 状态表示 (f(i,j))
- 集合
- 从起点走到((i,j))的所有路径
- 属性
- (max) (每个路径的长度)
- 集合
- 状态计算
- 来自左上方的一类、来自右上方的一类
- 来自左上方：(f(i-1,j-1)+a[i,j])
- 来自右上方：(f(i-1,j)+a[i,j])
- 转移方程 (f(i,j) = max(f(i-1,j-1)+a[i,j],f(i-1,j)+a[i,j]))
状态数量 (n^2)，转移计算量 (O(1))，时间复杂度 (O(n^2))
注意初始化部分，算最右侧点的时候，因为最右点不存在，需要初始化 -INF，左侧点同理
#include <algorithm> #include <iostream> using namespace std; int const N = 5e2 + 10, INF = 1e9; int a[N][N]; int f[N][N]; int n; int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) cin >> a[i][j]; for (int i = 0; i <= n; i++) for (int j = 0; j <= i + 1; j++) f[i][j] = -INF; f[1][1] = a[1][1]; for (int i = 2; i <= n; i++) for (int j = 1; j <= i; j++) f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]); int res = -INF; for (int i = 1; i <= n; i++) res = max(res, f[n][i]); cout << res; return 0; }
895 最长上升子序列
- 状态表示 (f(i))
- 集合
- 以序列第 (i) 个数（下标位置）结尾的所有上升子序列
- 属性
- (max) （每个上升子序列的长度）
- 集合
- 状态计算
- 第 (i) 个数已确定，根据第 (i-1) 个数是序列哪个数（下标位置）来分类
- (r = 0（只有 i 自己）、1、2、3...i-1)，前提是 (a_r < a_i)
- 转移方程 (f(i) = max(f(r) + 1))，(a_r < a_i)，(0 <= r <= i -1)
状态数量 n，转移数量 n ，故 (O(n^2))
#include <algorithm> #include <iostream> using namespace std; int const N = 1e3 + 10; int n; int a[N]; int f[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { f[i] = 1; // 只有 i 一个数的情况，也就是 j = 0 情况 for (int j = 1; j < i; j++) { if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1); } } int res = 0; for (int i = 1; i <= n; i++) res = max(res, f[i]); cout << res; return 0; }
如何保存最长序列
用一个数组存储状态的转移
#include <algorithm> #include <iostream> using namespace std; int const N = 1e3 + 10; int n; int a[N]; int f[N]; int g[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { f[i] = 1; // 只有 i 一个数的情况，也就是 j = 0 情况 g[N] = 0; for (int j = 1; j < i; j++) { if (a[j] < a[i]) { if (f[i] < f[j] + 1) { f[i] = f[j] + 1; g[i] = j; } } } } int res = 0, last = 0; // last 标记最长子序列末尾位置 for (int i = 1; i <= n; i++) { if (f[i] > res) { res = f[i]; last = i; } } cout << res << endl; cout << "路径" << endl; for (int i = 1; i <= res; i++) { cout << a[last] << " "; last = g[last]; } return 0; }
896⭐最长上升子序列2
贪心。定义一个数组，存储所有不同长度上升子序列结尾的最小值，随长度增加，结尾最小值单调递增。每次插入一个 (a_i) 整数二分查找（小于某个数的最大的数），返回长度并更新数组。时间复杂度 (O(nlog_2n))。不是DP做法
#include <algorithm> #include <iostream> using namespace std; int const N = 1e5 + 10; int n; int a[N]; int q[N]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; int len = 0; q[0] = -2e9; for (int i = 0; i < n; i++) { int l = 0, r = len; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] < a[i]) l = mid; else r = mid - 1; } len = max(len, r + 1); q[r + 1] = a[i]; } cout << len; return 0; }
897 最长公共子序列
-
状态表示 (f(i,j))
- 集合
- 在第一个序列的前 (i) 个字母中出现，且在第二个序列的前 (j) 个字母中出现的所有公共子序列
- 属性
- max (每个公共子序列的长度 )
- 集合
-
状态计算
-
a[i]、b[j] 是否包含在公共子序列当中作为划分依据（四种情况）(不出现和必须出现)
-
00：(f(i-1,j-1)) （这一类情况被包含在01 | 10内）
-
01：(f(i-1,j))
- (f(i-1,j)) 包含 01 的情况，求 max 是可以重复的（求数量不能重复）
-
10：(f(i,j-1))，同理
-
11：(f(i-1,j-1)+1)
- 前提是 a[i] == b[j]
-
一般只考虑 01、10、11 三种情况。状态数量 (n^2) ，状态转移计算 3 次，时间复杂度 (O(n^2))
因为需要从(i-1)层开始算，下标从1开始读
#include <algorithm> #include <iostream> using namespace std; int const N = 1e3 + 10; int n, m; char a[N], b[N]; int f[N][N]; int main() { cin >> n >> m; scanf("%s%s", a + 1, b + 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = max(f[i - 1][j], f[i][j - 1]); if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); } } cout << f[n][m] << endl; return 0; }
902⭐最短编辑距离
- 状态表示 (f(i,j))
- 集合
- 将a[1~i]变成b[1~j]的所有操作方案
- 属性
- min （每个方案的操作次数）
- 集合
- 状态计算：按最后一次操作分类
- 删 (f(i-1,j) + 1)
- 增 (f(i,j-1) + 1)
- 改 (f(i-1,j-1) + 1/0) （看a[i]是否等于b[j]）
状态数量 (n^2) ，状态转移计算 3 次，时间复杂度 (O(n^2))
https://www.acwing.com/solution/content/5607/
相信很多人都是这么考虑问题的：dp[i][j]为 a 的 [0..i] 转换成 b 的 [0..j] 的最小操作数。
if (删除的情况) dp[i][j] = dp[i-1][j] + 1; else if (新增的情况) dp[i][j] = dp[i][j-1] + 1; else if (修改的情况) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = dp[i-1][j-1]; // 不需要任何操作, 和上一个状态相同 注意，这种考虑方式不需要写 min，因为你准确的描述了各种情况。
这样想其实是没有毛病的，但是难点在于你无法把 () 中的情况准确的用代码表达出来。
能描述出来的只有 不需要操作 这种情况，若 a[i] == b[j] 则无需修改，其余情况难以准确的描述。
但这题其实求的是 最短编辑距离，突出了一个最短，所以以上情况完全可以归纳为：
// 无需操作 if (a[i] == b[j]) dp[i][j] = dp[i-1][j-1]; // 新增, 删除, 修改 都是可以到当前状态的, 我只管取其中最小值就行 else dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
#include <algorithm> #include <cstdio> #include <iostream> using namespace std; int const N = 1e3 + 10; int n, m; char a[N], b[N]; int f[N][N]; int main() { // scanf("%d%s", &n, a + 1); // scanf("%d%s", &m, b + 1); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; cin >> m; for (int i = 1; i <= m; i++) cin >> b[i]; // 初始化 0 // 只添加 for (int i = 0; i <= m; i++) f[0][i] = i; // 只删除 for (int i = 0; i <= n; i++) f[i][0] = i; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); } } cout << f[n][m]; return 0; }
899 编辑距离
注意下标从 1 开始
#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 15, M = 1e3 + 10; int n, m; int f[N][N]; char str[M][N]; int edit_distance(char a[], char b[]) { int la = strlen(a + 1), lb = strlen(b + 1); for (int i = 0; i <= lb; i++) f[0][i] = i; for (int i = 0; i <= la; i++) f[i][0] = i; for (int i = 1; i <= la; i++) { for (int j = 1; j <= lb; j++) { f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j])); } } return f[la][lb]; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> (str[i] + 1); while (m--) { char s[N]; int limit; cin >> (s + 1) >> limit; int res = 0; for (int i = 0; i < n; i++) if (edit_distance(str[i], s) <= limit) res++; cout << res; } return 0; }
区间DP
282 石子合并
- 状态表示 (f(i,j)) 第 (i) 堆到第 (j) 堆的区间
- 集合
- 将第 i 堆石子到第 j 堆石子合并成一堆石子的所有合并方式
- 属性
- (min) （每种合并方式的总代价 ）
- 集合
- 状态计算
- 以最后一次合并的分界线来分类（两堆合成一堆的分界线）
- 左堆个数，右堆个数：1，k-1 | 2，k-2 | ... | k-1，1
- 设分界线为k，先不考虑最后合并步骤，然后再加上最后合并的代价
- 此时分为两堆 ([i,k],[k+1,j])
- (f(i,j)=Min(f(i,k)+f(k+1,j)+s[j]-s[i-1])) ，后部分是前缀和求区间和
- 左堆合并最小代价+右堆合并最小代价+最后合并的代价
- (kin[i,j-1])
状态数量 (n^2) ，状态转移计算 n 次，时间复杂度 (O(n^3))。按区间长度从小到大枚举，从2到n
#include <algorithm> #include <iostream> using namespace std; int const N = 3e2 + 10; int n; int s[N]; int f[N][N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> s[i]; for (int i = 1; i <= n; i++) s[i] += s[i - 1]; for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int l = i, r = i + len - 1; f[l][r] = 1e9; // 求min，初始化，不然每次都是 0 for (int k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); } } cout << f[1][n]; return 0; }
计数DP
900⭐整数划分
通用解法
- 状态表示 (f(i,j))
- 集合
- 考虑前 (i) 个物品，物品总体积恰好为 j 的所有方案。完全背包
- 属性
- (count)
- 集合
- 状态计算
- 不选第 i 个：(f(i-1,j))
- 选 i 的 k 个：(f(i-1,j-V_i*k))，优化为 (f(i,j-V_i))
- 转移方程：(f(i,j) = f(i-1,j) + f(i,j-V_i))
#include <algorithm> #include <iostream> using namespace std; int const N = 1e3 + 10; int n; int v[N]; unsigned f[N]; int main() { cin >> n; f[0] = 1; unsigned mod = (1e9 + 7); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { f[j] = (f[j] + f[j - i]) % mod; } } cout << f[n]; return 0; }
另类解法
- 状态表示 (f(i,j))
- 集合
- 总和是 (i) ，并且恰好表示成 (j) 个数的和的所有方案
- 属性
- (count)
- 集合
- 状态计算
- j 个数里最小值是 1
- (f(i-1,j-1))
- j 个数里最小值大于 1
- 把每一个数都减去一个1
- (f(i-j,j))
- (f(i,j) = f(i-1,j-1) +f(i-j,j))
- j 个数里最小值是 1
#include <algorithm> #include <iostream> using namespace std; unsigned mod = (1e9 + 7); int const N = 1e3 + 10; int n; int f[N][N]; int main() { cin >> n; f[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod; } } int res = 0; for (int i = 1; i <= n; i++) { res = (res + f[n][i]) % mod; } cout << res; return 0; }
状态压缩DP
用一个 (n) 位二进制数，每一位表示一个物品，0/1 表示不同的状态。因此可以用 ([0,2^n − 1]) 中的所有数来枚举全部状态
291 蒙德里安的梦想
摆放长方形的时候，先放横着的，再放竖着的，确保能放满。总方案数等于只放横着小方块的合法方案数
- 状态表示 (f(i,j))
- 集合
- 已将前 i -1 列摆好，且从第 i − 1 列伸出到第 i 列的状态是 j 的所有方案
- 状态 j 是二进制串，当前列每个格子的状态如 101001（1代表前一列该行放了长方形）
- 属性
- (count)
- 集合
- 状态计算
- 第 i - 1 列状态 k ，第 i 列状态 j
- 转移方程 (f(i,j) = sum f(i-1,k))
- j 与 k 需满足
- 没有重行
(j & k) == 0 - k 与 j 并集后的状态连续 0 数量不是奇数
st[j | k]
- 没有重行
- 预处理
j | k所有可能的状态，也就是 ([1,2^n))，判断每个状态是否出现了奇数个连续0，若出现 st[i] 设置为false f[0][0] = 1根据状态表示，-1 层并不存在，横着摆放长方形个数为 0，那么只有竖着摆放一个方案f[m][0]是最终结果，此时摆放好了 ([0,m-1]) 层，总共 m 层，第 m 层不能横着放长方形，因此 j 为 0
#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 12, M = 1 << N; int n, m; long long f[N][M]; bool st[M]; int main() { int n, m; while (cin >> n >> m, n || m) { memset(f, 0, sizeof f); // 预处理，列举所有状态,连续0为奇数的状态置为True for (int i = 0; i < (1 << n); i++) { st[i] = true; int cnt = 0; for (int j = 0; j < n; j++) { if (i >> j & 1) { if (cnt & 1) { st[i] = false; break; } cnt = 0; } else cnt++; } if (cnt & 1) st[i] = false; } // DP f[0][0] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j < 1 << n; j++) { for (int k = 0; k < 1 << n; k++) { if ((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k]; } } } cout << f[m][0] << endl; } return 0; }
91 最短Hamilton路径
朴素做法时间复杂度 (O(n!*n))：最坏情况下全排列，然后每个排列算一遍长度，肯定TLE
- 状态表示 (f(i,j))
- 集合
- 所有从 (0) 点走到 (j) 点，走过的所有点是 (i) 的所有路径
- (i) 是二进制数，每一位表示当前点是不是走过
- 属性
- (min) （每个路径的长度）
- 集合
- 状态计算
- 枚举倒数第二个点是哪个点 (kin[0,n-1])
- (f(i-{ j },k)) 所有从 0 走到 k 且不经过 j 的点的所有路径的最短距离
- 转移方程 (f(i,j) = min(f(i-{ j },k) + a(k,j)))
- 从 0 开始走，0 点在二进制1号位，所以
f[1][0] = 0
#include <bits/stdc++.h> using namespace std; const int N = 20, M = 1 << 20; int n; int w[N][N]; int f[M][N]; int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cin >> w[i][j]; } // 求min，初始化 memset(f, 0x3f, sizeof f); f[1][0] = 0; for (int i = 0; i < 1 << n; i++) { for (int j = 0; j < n; j++) { // i 是否记录已走过 j 点 if (i >> j & 1) for (int k = 0; k < n; k++) { // i 记录了 k 点 if (i >> k & 1) f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]); } } } cout << f[(1 << n) - 1][n - 1] << endl; return 0; }
树形DP⭐
285 没有上司的舞会
- 状态表示 (f(u,0)) (f(u,1))
- 集合
- (f(u,0)) 以 u 为根的子树中选择，并且不选 u 这个点的所有方案
- (f(u,1)) 以 u 为根的子树中选择，并且选 u 这个点的所有方案
- 属性
- (max) （每个方案的快乐指数）
- 集合
- 状态计算 （(si) 为 u 的所有儿子）
- (f(u,0) = sum Max(f(si,0),f(si,1)))
- (f(u,1) = sum f(si,0))
所有节点总儿子数量等于边数 n - 1 ，整个问题时间复杂度 (O(n))
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 6e3 + 10; int n; int happy[N]; int h[N], e[N], ne[N], idx; int f[N][2]; bool has_father[N]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u) { f[u][1] = happy[u]; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += max(f[j][0], f[j][1]); f[u][1] += f[j][0]; } } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> happy[i]; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; has_father[a] = true; add(b, a); } int root = 1; while (has_father[root]) root++; dfs(root); cout << (max(f[root][0], f[root][1])) << endl; return 0; }
记忆化搜索
每一道动态规划问题都可以用递归方式来写（如上面的树形DP）
901 滑雪
- 状态表示 (f(i,j))
- 集合
- 从 (i,j) 开始滑的所有路径
- 属性
- (max) （每个路径的长度）
- 集合
- 状态计算
- 按第一步往哪个方向滑分为四类（即先不考虑第一步，再考虑第一步）
- 往右划： (f(i,j+1) + 1) ，其他同理（要考虑存在条件，滑到点高度小于当前点）
同时递归不应该存在环。题目能满足要求（点与点的高度差关系）
#include <algorithm> #include <cstring> #include <iostream> using namespace std; int const N = 3e2 + 10; int n, m; int h[N][N]; int f[N][N]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int dp(int x, int y) { int &v = f[x][y]; if (v != -1) return v; v = 1; // 不能走，路径为1 for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && h[nx][ny] < h[x][y]) { v = max(v, dp(nx, ny) + 1); } } return v; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> h[i][j]; memset(f, -1, sizeof f); int res = 0; // 遍历每一个起点的最大值 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) res = max(res, dp(i, j)); cout << res; return 0; }
参考资料
感谢所有大佬的题解，所有博客知识分享。ORZ
OI Wiki - OI Wiki (oi-wiki.org)
AcWing 11. 背包问题求方案数【背包DP求最优方案总数】
背包问题中 体积至多是 j ，恰好是 j ，至少是 j 的初始化问题的研究
AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】 - AcWing
AcWing 291. 蒙德里安的梦想（详细注释 ） - AcWing
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
