什么是动态规划
如果一个最优化问题可以被分成一系列最优化的子问题后再合并，那么这个最优化问题可能就需要一个动态规划算法。
一个问题里面的多个解通常都会有一些共性，对于共性相同的解，我们可以将他们用共性表示出来，并且取他们的最优值。
我们称这些解的集合为一个“状态”。
比如说我们要求 1 4 2 8 5 7 这个序列的最长上升子序列，我们可以用 S[i][j] 表示所有由前 $i$ 个数所构成的 “最后一个数是 $j$” 的上升子序列，接着用 f[i][j] 表示 S[i][j] 里面最长的上升子序列的长度。
这样我们就可以称 f[i][j] 为一个状态，它表征的是所有“用前 $i$ 个数构成的最后一个数是 $j$ 的最长的上升子序列的长度”。
动态规划的本质
动态规划是一种思想：
通过对原问题划分子问题，寻找子问题之间的联系，通过求解子问题得出原问题的解
子问题 对应 状态
子问题之间的联系 对应 状态转移
边界子问题 对应边界状态（状态转移的边界）
边界子问题：其结果不依赖其他子问题
$\color{red}{\text{同一个问题的不同解法可能有不同的边界，任何解法一定有边界}}$
动态规划的状态和转移
对于存在最优子结构的问题而言，我们可以拆分最优解所对应的状态，然后在拆分出来的状态里面取最优的，这样就得到最后的最优解。
仍以 LIS 问题举例，记 f[i][j] 所表征的那个最长的子序列为 $L$，那么如果把 $L$ 的最后一个数删掉，就是一个长度为 $|L| - 1$ 的上升子序列，这样他就一定是某个 f[i - 1][x] (因为他一定是最长的)。
当然也可能 $L$ 本身就是某个 f[i - 1][x]，因为我们用前 $i - 1$ 个数构成的最优解仍然可能是由前 $i$ 个数构成的最优解。
于是我们可以得到 f[i][j] 的递推式：
$$ f[i][j] = \max\{f[i - 1][j], f[i - 1][k] + 1 | k < j \& j == a[i]\} $$
这个递推式里，从一个状态到另一个状态的计算，我们称之为“转移”。
动态规划，就是状态和转移的世界。
动态规划的类型有太多太多，我们从例题来体会状态和转移的巧妙。
按照常用套路的不同，可以对动态规划进行如下分类：
- 一维动归
- 背包动归
- 区间动归
- 树形动归
- DAG 动归
一维动归
$N$ 个物品排成一排，从中选出若干个
选出的物品之间需要满足一定的条件
求一个最优的选择方案
如：$\rm{LIS}$，条件：选出的数是递增的，最优：选出尽量多的数
$\rm{LIS}$ 的变形：
$\color{blue}{选出尽量多递减（相等）的数}$
$\color{blue}{选出尽量多和（乘积）不超过 W 的数}$
$\color{blue}{选出尽量少和超过 W 的数}$
dp[i] 表示第 $i$ 个物品的最优方案
dp[i][0/1] 表示前 $i$ 个物品，其中第 $i$ 个物品是否被选中，此时的最优方案
dp[i][k] 表示前 $i$ 个物品，选出 $k$ 个的最优方案
例题1：最长上升子序列（LIS）
给定一个整数序列 A[1...n]，求其最长上升子序列的长度。
$n \leqslant 1000, 1 \leqslant A[i] \leqslant n$。
我们前面已经分析过它的转移方程。
那么我们可以根据转移方程进行递推，计算出最优解。
时间复杂度为 $O(n^2)$。
给定一个整数序列 A[1...n]，求其最长上升子序列的长度。
$n \leqslant 10^5$。
诚然我们求出了一个解，但是这个解法未免有些慢。
我们有没有更好的方式计算答案？
注意到我们的转移过程是一个求“区间最小值”的过程。同时，我们只会对 f[i][a[i]] 这个位置的值进行修改，其他所有位置都有 f[i][x] = f[i - 1][x] 。
这意味着这是一个单点修改，区间查询的问题，学了线段树之后这些都可以在 $O(\log n)$ 的时间内完成。
利用线段树后可以将总复杂度变为 $O(n\log n)$。
我们刚才对转移过程进行了优化。有没有其他优化方式？
考虑另外一种表示状态的方式。
g[i][j] 表示所有“只用前 $i$ 个数的长度为 $j$ 的上升子序列”里，序列里最后一个数的最小值。
会使用这种方式是因为我们肯定希望子序列的最后一个数越小越好，只有越小才能往后接更多的数。
那么
$$ g[i][j] = \min\{g[i - 1][j], a[i] \big| g[i - 1][j - 1] < a[i]\} $$
但是这样仍然是有 $O(n^2)$ 个状态需要计算转移呀？看起来好像没有任何优化喔？
我们考虑 g[i][j] 本身的性质，会发现一定有 $g[i][j - 1] \leqslant g[i][j]$。
如果 $g[i][j - 1] > g[i][j]$，那么我们可以取 $g[i][j]$ 表示的那个序列 $L$，然后将其删掉最后一位，得到一个长度为 $j - 1$ 的序列 $L’$，而 $L’$ 的最后一位小于 $g[i][j] < g[i][j - 1]$，和 $g[i][j - 1]$ 的定义矛盾。
这个性质有什么用呢？
我们注意到，$a[i]$ 只能给一个位置更新。
因为单调性，只能有 $g[i - 1][x - 1] < a[i] < g[i - 1][x]$，这个时候就可以对 $g[i - 1][x]$ 进行更新。
所以我们的策略就是直接维护一个一维数组 $g$，然后每次用 $a[i]$ 更新的时候在 $g$ 里面进行二分查找，找到对应的更新位置。
总时间复杂度也是 $O(n\log n)$ 的。
例题2：选数
有 $N$ 个数排成一排，从中选出恰好 $k$ 个数，相邻的两个数最多选一个
要求选出的数之和最大
例：1 4 5 3 1 7
选 $1$ 个：$7$
选 $2$ 个：$5 \ 7$
选 $3$ 个：$4 \ 3 \ 7$
分析：
dp[i][j]：从前 $i$ 个数中选择恰好 $j$ 个数的最优方案
可以把条件 相邻的两个数最多选一个 体现在转移中
转移方程：
$dp[i][j] = \max(dp[i-1][j], dp[i-2][j-1] + data[i])$
边界：
将不可能的方案设置为 -INF
$\color{blue}{无法从 a 个数中选出 b 个不相邻的数}$
dp[0][*] = -INF
dp[0][0] = 0
另一种状态定义的方式：
dp[i][k][s]：从前 $i$ 个数选出 $k$ 个数，其中 $s$ 表示第 $i$ 个数是否被选中 (0/1)
状态转移：
$dp[i][k][0] = \max(dp[i-1][k][0], dp[i-1][k][1])$
$dp[i][k][1] = a[i] + dp[i-1][k-1][0]$
边界：
$dp[\*][0][0] = 0$
$dp[\*][0][1] = -\rm{INF}$
答案为 $\max(dp[n][k][0], dp[n][k][1])$
例题3：数字组合
分析：
题目要求从有 $n$ 个正整数中选择若干个数，其和为 $t$ 的方案有多少个。
dp[i][j] 表示前 $i$ 个数中和为 $j$ 的方案数。
对于第 $i$ 个数的处理状态：
- 不选择第 $i$ 个数，方案数仍为 $dp[i - 1][j]$
- 选择第 $i$ 个数，选择第 $i$ 个数之前的和为 $j - a[i]$，相当于从第 $i - 1$ 阶段向第 $i$ 阶段转化。
问题就转化为“从 $i - 1$ 个数中和为 $j - a[i]$ 的方案数”，即 $dp[i - 1][j - a[i]]$。
前 $i$ 个数中和为 $j$ 的方案数为两种方案数之和：
$$ dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]] $$
仿照 $01$ 背包用一维数组优化，倒推即可。
Code:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
const int N = 1010;
int a[N];
int dp[N]; // dp[i]表示和为i的存组合方式数
int main() {
int n, t;
cin >> n >> t;
rep(i, n) cin >> a[i];
dp[0] = 1;
rep(i, n) { // 实际上是01背包
for (int j = t; j >= a[i]; --j) // 倒推
dp[j] += dp[j - a[i]];
}
cout << dp[t] << '\n';
return 0;
}
例题4：多米诺骨牌
分析：
因为我们只能互换上下两个方块的位置，所以如果我们知道了某一行的和，我们就直到了另外一行的和。
考虑 f[i][j] 表示前 $i$ 列里，上面一行的和为 $j$ 的最小旋转次数。
那么我们就可以枚举第 $i$ 列是否旋转，来得到转移。设第 $i$ 个牌的上面为 $a[i]$，下面为 $b[i]$。
$$ f[i][j] = \min\{f[i - 1][j - a[i]], f[i - 1][j - b[i]] + 1\} $$
最后只需要看 $f[n]$ 里哪个状态的点数之差是最小的就可以了。
时间复杂度 $O(n^2)$。
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::abs;
bool chmin(int& a, int b) { if (a > b) { a = b; return 1; } return 0; }
const int N = 1010;
const int M = N * 6;
int a[N], b[N];
int f[N][M];
int main() {
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i];
sum += a[i] + b[i];
}
const int INF = 1001001001;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= 6 * n; ++j)
f[i][j] = INF;
f[1][a[1]] = 0; f[1][b[1]] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= 6 * n; ++j) {
if (j >= a[i]) chmin(f[i][j], f[i - 1][j - a[i]]);
if (j >= b[i]) chmin(f[i][j], f[i - 1][j - b[i]] + 1);
}
}
int d = INF, ans = INF;
for (int j = 0; j <= sum; ++j) {
if (f[n][j] != INF) {
if (abs(sum - 2 * j) < d) {
d = abs(sum - 2 * j);
ans = f[n][j];
}
else if (abs(sum - 2 * j) == d) {
chmin(ans, f[n][j]);
}
}
}
cout << ans << '\n';
return 0;
}
背包动归
说到 $\rm DP$，就不得不提背包问题了。
背包动归是特殊的一维动归
$N$ 个物品，每个物品有价值和体积两个属性
从中选出若干个物品，体积和不超过 $V$（条件）
要求选出的物品价值和最大（最优化目标）
体积可能是多维（多维背包）
物品可以被选的次数可能是有限次或者无限次（多重背包、完全背包）
物品之间可能存在依赖（依赖背包）
01 背包
有一个容量为 $m$ 的背包，有 $n$ 个物品，第 $i$ 个物品有体积 $w[i]$ 和价值 $v[i]$，你需要在容量限制的情况下把物品装入背包，使得背包内的物品价值最大。
$m \leqslant 1000, n \leqslant 100$
我们可以用 $f[i][j]$ 表示前 $i$ 个物品中，选出体积和为 $j$ 的物品组合的最大价值。
容易写出 $f[i][j] = \max\{f[i - 1][j], f[i - 1][j - v[i]] + w[i]\}$
直接利用这个石子进行转移和计算，时间和空间复杂度都是 $O(mn)$。
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
bool chmax(int& a, int b) { if (a < b) { a = b; return 1; } return 0; }
const int N = 1010;
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)
chmax(f[j], f[j - v[i]] + w[i]);
cout << f[m] << '\n';
return 0;
}
多重背包
有一个容量为 $m$ 的背包，有 $n$ 种物品，第 $i$ 种物品有 $c[i]$ 个，体积为 $v[i]$ 价值为 $w[i]$，你需要在容量限制的情况下把物品装入背包，使得背包内的物品价值最大。
$m \leqslant 1000$，$n \leqslant 100$。
仿照 $01$ 背包的做法，我们可以写出
$$ f[i][j] = \max\{f[i - 1][j], f[i - 1][j - v[i] * k] + w[i] * k \ | \ k * v[i] \leqslant j \& k \leqslant c[i]\} $$
这样的时间复杂度是 $\displaystyle O(m\sum_{i = 1}^n c[i])$。
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
bool chmax(int& a, int b) { if (a < b) { a = b; return 1; } return 0; }
const int N = 110;
int n, m;
int f[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
int v, w, s;
cin >> v >> w >> s;
for (int j = m; j >= 0; --j) {
for (int k = 1; k <= s and k * v <= j; ++k)
chmax(f[j], f[j - k * v] + k * w);
}
}
cout << f[m] << '\n';
return 0;
}
这样 $c[i]$ 很大的时候这个算法会很慢。有没有什么优化的办法？
因为物体是一样的，所以我们可以尝试将他们捆绑起来。
比方说如果一个物品有 $7$ 个，那么我们可以把它们捆绑成三堆，分别是 $1$ 个、$2$ 个、$4$ 个。
这样对于 $1 \sim 7$ 的任何一种数量，我们都可以从那三堆里抽几堆出来凑成我们要的数量。
实际上，对于第 $i$ 种物品，我们可以将 $c[i]$ 的这个数量给拆成 $\displaystyle 1, \ 2, \ 4, \cdots, 2^i,\ \cdots, 2^k, \ c[i] - \sum_{j = 0}^k 2^j$ 这些数量，每堆捆绑在一起放进背包。
这样就是说，对于 $1 \sim c[i]$ 中的任何一种数量，我们都可以从捆绑出来的这些物品选择一些组合来得到。
于是我们就将 $c[i]$ 个物品组合成了 $O(\log c[i])$ 个不同的物品。
接着我们用 $01$ 背包解决即可。
时间复杂度：$O(m\sum\log c)$。
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
bool chmax(int& a, int b) { if (a < b) { a = b; return 1; } return 0; }
const int N = 2010;
int n, m;
int f[N];
struct Good {
int v, w;
};
int main() {
vector<Good> goods;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k <= s; k *= 2) {
s -= k;
goods.push_back({k * v, k * w});
}
if (s > 0) goods.push_back({s * v, s * w});
}
for (auto good : goods)
for (int j = m; j >= good.v; --j)
chmax(f[j], f[j - good.v] + good.w);
cout << f[m] << '\n';
return 0;
}
完全背包
有一个容量为 $m$ 的背包，有 $n$ 种物品，第 $i$ 种物品有无限个，体积为 $w[i]$ 价值为 $v[i]$，你需要在容量限制的情况下把物品装入背包，使得背包内的物品价值最大。
$m \leqslant 1000,\ n \leqslant 100$。
仿照多重背包的做法，我们可以写出
$$ f[i]][j] = \max\{f[i - 1][j], f[i - 1][j - v[i] * k] + w[i] * k \big| k * v[i] \leqslant j\} $$
这和多重背包的转移方程好像是一模一样的啊？
实际上，每种物品有 $\frac{m}{v[i]}$ 个。否则再多就会爆炸。
于是转化成多重背包解决。
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
bool chmax(int& a, int b) { if (a < b) { a = b; return 1; } return 0; }
const int N = 1010;
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) {
chmax(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << '\n';
return 0;
}
分组背包
有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的费用是 $c[i]$，价值是 $w[i]$。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法：
这个问题变成了每组物品有若干种策略：是选择本组中的某一件，还是一件都不选。也就是说设 $f[k][v]$ 表示前 $k$ 组物品花费费用 $v$ 能取得的最大价值，则有：$f[k][v] = \max\{f[k - 1][v], f[k - 1][c - v[i]] + w[i] | 物品 $i$ 属于第 $k$ 组\}$。使用一维数组的伪代码如下：
for 所有的组k
for v=V...0
for 所有的 i 属于组k
f[v] = max{f[v], f[v - c[i]] + w[i]}
Code:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
bool chmax(int& a, int b) { if (a < b) { a = b; return true; } return false; }
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
rep(j, s[i]) cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; ++i)
for (int j = m; j >= 0; --j)
rep(k, s[i]) {
if (v[i][k] <= j)
chmax(f[j], f[j - v[i][k]] + w[i][k]);
}
cout << f[m] << '\n';
return 0;
}
例题：金明的预算方案
想买的物品分为两类：主件和副件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机、扫描仪
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。附件不再有从属于自己的附件。
每组的决策可以是：什么都不要，主要主件，要主件和附件 $1$，要主件和附件 $1$，要主件和附件 $1, 2$
Code:
#include <bits/stdc++.h>
#define v first
#define w second
using std::cin;
using std::cout;
using std::max;
using std::vector;
using P = std::pair<int, int>;
const int N = 70, M = 32010;
int n, m;
P master[N];
vector<P> servent[N];
int f[M];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int v, w, q;
cin >> v >> w >> q;
if (!q) master[i] = {v, v * w};
else servent[q].push_back({v, v * w});
}
for (int i = 1; i <= m; ++i) {
for (int j = n; j >= 0; --j)
for (int k = 0; k < 1 << servent[i].size(); ++k) {
int v = master[i].v, w = master[i].w;
for (int u = 0; u < servent[i].size(); ++u)
if (k >> u & 1) {
v += servent[i][u].v;
w += servent[i][u].w;
}
if (j >= v) f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[n] << '\n';
return 0;
}
二维费用背包问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种费用。对于每种费用都有一个可付出的最大价值（背包容量）。问怎样选择物品可以得到最大的价值。设第 $i$ 件物品所需的两种费用分别为 $C_i$ 和 $D_i$。两种费用可付出的最大值（也即两种背包容量）分别为 $V$ 和 $U$。物品的价值为 $W_i$。
费用加了一维，只需状态也加一维即可。设 $F[i][v][u]$ 表示前 $i$ 件物品付出两种费用分别为 $v$ 和 $u$ 时可获得的最大价值。状态转移方程就是：
$$ F[i][v][u] = \max\{F[i - 1][v][u], F[i - 1][v - C_i][u - D_i] + W_i\} $$
如前述优化空间复杂度的方法，可以只使用二维的数组：当每件物品只可以取一次时临时变量 $v$ 和 $u$ 采用逆序的循环，当物品有如完全背包问题时采用顺序的循环，当物品有如多重背包时拆分物品。
Code:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
bool chmax(int& a, int b) { if (a < b) { a = b; return true; } return false; }
const int N = 110;
int n, V, M;
int f[N][N];
int main() {
cin >> n >> V >> M;
rep(i, n) {
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; --j)
for (int k = M; k >= m; --k)
chmax(f[j][k], f[j - v][k - m] + w);
}
cout << f[V][M];
return 0;
}
混合背包
如果将 01背包、完全背包、多重背包混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包）、有的物品可以取有限次（多重背包）。
应该怎么求解呢？
01背包与完全背包的混合：
考虑到在01背包和完全背包中的代码实现只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的选用顺序或逆序的循环即可，复杂度是 $O(VN)$。
伪代码如下：
for i = 1...N
if 第 i 件物品是01背包
for v = V...0
f[v] = max(f[v], f[v-w[i]]+c[i])
else if 第 i 件物品是完全背包
for v = 0...V
f[v] = max(f[v], f[v-w[i]+c[i])
再加上多重背包
如果再加上有的物品可以取有限次，那么原则上也可以给出 $O(VN)$ 的解法：遇到多重背包类型的物品用单调队列或二进制优化解即可。
例题： 混合背包问题
Code:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int MX = 1005;
int dp[MX];
struct Goods {
int kind;
int v, w;
};
inline void chmax(int &x, int y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
vector<Goods> gs;
rep(i, n) {
int v, w, s;
cin >> v >> w >> s;
if (s == -1) gs.push_back({-1, v, w});
else if (s == 0) gs.push_back({0, v, w});
else {
for (int k = 1; k <= s; k *= 2) {
s -= k;
gs.push_back({-1, v*k, w*k});
}
if (s > 0) gs.push_back({-1, v*s, w*s});
}
}
for (auto g : gs) {
if (g.kind == -1) {
for (int j = m; j >= g.v; --j) chmax(dp[j], dp[j-g.v] + g.w);
}
else {
for (int j = g.v; j <= m; ++j) chmax(dp[j], dp[j-g.v] + g.w);
}
}
cout << dp[m] << '\n';
return 0;
}
背包问题求具体方案
Code:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n); i >= 1; --i)
using std::cin;
using std::cout;
const int MX = 1005;
int dp[MX][MX];
int v[MX], w[MX];
inline void chmax(int &x, int y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
rep(i, n) cin >> v[i] >> w[i];
drep(i, n)rep(j, m) {
dp[i][j] = dp[i+1][j];
if (j >= v[i]) chmax(dp[i][j], dp[i+1][j-v[i]] + w[i]);
}
int i = 1, j = m;
while (i <= n) {
if (j >= v[i] and dp[i+1][j-v[i]] + w[i] >= dp[i+1][j]) {
cout << i << " ";
j -= v[i];
i++;
}
else i++;
}
return 0;
}
区间DP
例题：石子合并
有 $n$ 堆石子排成一排，第 $i$ 堆石子有 $a_i$ 颗，你每次可以选择两堆相邻的石子合并成一堆，并且花费的代价为这两堆石子的总数。
目标是将所有的石子都合并成一堆，并且花费的代价最小/最小。$n \leqslant 100$。
最小最大问题几乎是等价的，下面我们只讨论最小化。
记 $s[i]$ 为石子堆数的前缀和， $f[i][j]$ 表示将区间 $[i, j]$ 中的石子合并成一堆所花费的最小代价，容易写出：
$$ f[i][j] = \min\{f[i][k] + f[k + 1][j]\} + s[j] - s[i - 1] $$
怎么递推计算？
大的区间可以由小的区间得到。我们希望在计算大的区间的时候已经计算出小的区间了。
所以从小到大枚举区间来进行递推。
从小到大枚举区间长度，然后枚举区间的起点。这样就可以计算状态的值了。
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
template<typename T1, typename T2> bool chmin(T1& a, const T2& b) { if (a > b) { a = b; return 1; } return 0; }
const int N = 310;
const int INF = 1001001001;
int n;
int s[N]; // 前缀和
int f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> s[i], s[i] += s[i - 1];
for (int len = 2; len <= n; ++len) {
for (int i = 1; i + len - 1<= n; ++i) {
int j = i + len - 1;
f[i][j] = INF;
for (int k = i; k < j; ++k)
chmin(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
cout << f[1][n] << '\n';
return 0;
}
我们还有一种更直接的思路。
我们能不能直接调用一个函数 $dp(l, r)$ 就能返回 $f[l][r]$ 的值？
这样就是一个搜索。每次计算完 $dp(l, r)$ 的值后，将其记录在 $f[l][r]$ 内，这样下次调用 $dp(l, r)$ 时也能快速返回正确的值。
这就是记忆化搜索，这样的写法更加直观。
Code:
// f[l][r]
int dp(int l, int r) {
if (f[l][r] != -1) return f[l][r];
if (r - l + 1 == 1) return 0;
int t = 0x7fffffff;
for (int k = 1; k < r; ++k)
t = min(t, dp(l, k) + dp(k + 1, r));
t += s[r] - s[l - 1];
return f[l][r] = t;
}
数位 DP
问题的一般形式是这样的：
定义一个条件 $A$，比如：被 $7$ 整除、数位中含有 $3$ 等等
询问区间 $[L,R]$ 中有几个数满足条件 $A$
$L$ 和 $R$ 的范围一般非常大，比如 $10^{18}$
通过数位 $\rm DP$，我们会发现这些问题的规模实际上是 $\log_{10} R$
数位 $\rm DP$ 就是考虑数字的每一位
问题的规模变为 $\log_{10} N$
每一位作为不同的阶段，设计状态
我们从高位往低位依次枚举。
（为什么不选择从低位到高位？）
每一位的数选择的范围是不同的，依据前面选的数决定。
比如 $N$ 是 $1230$
假设前两位枚举的数是 $1$ 和 $2$，也就是计算了 $12$ 开头的贡献
此时枚举第三位，可选的范围只有 $0 \sim 3$
如果前两位枚举的数是 $1$ 和 $0$
此时枚举第三位，可选的范围就是 $0 \sim 9$
因此我们用一个变量 $eq$ 或者 $less$，表示在枚举当前位之前，
每一位是不是都和 $N$ 选的一样
当前设为第 $dep$ 位，$N$ 的第 $dep$ 位为 $A[dep]$，假设填上 $k$
如果采用 eq 变量：
eq = eq && (A[dep] == k)
可选的最大值是 $eq \ ? \ A[dep] \ : \ 9$
如果采用 less 变量：
less = less || (k < A[dep])
可选的最大值是 $less \ ? \ 9 \ : \ A[dep]$
为了直观的理解数位 $\rm DP$，我们介绍记忆化搜索的形式
高位的答案由低位的答案转移而来
例题：同类分布 link
询问 $[L,R]$ 中各位数字之和能整除原数的个数
$1 \leqslant L \leqslant R \leqslant 10^{18}$
分析：
- 可以发现各位数之和最大只能是 $9 * 18 = 162$
- 我们可以枚举这个和 $sum$
- 然后去统计可以被 $sum$ 整除，且数位和是 $sum$ 的数
- 我们把状态定义为 $f[dep][cur][mod]$
- 表示当前枚举到第 $dep$ 位，目前这个数的数位和是 $cur$，对 $sum$ 取模是 $mod$
- $cur = sum$ 且 $mod = 0$ 的个数要统计进答案
Code:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
int a[22], sum;
ll f[22][170][170];
ll dp(int eq, int dep, int cur, int mod) {
if (cur > sum) return 0;
if (!dep) return mod == 0 and cur == sum;
if (!eq and ~f[dep][cur][mod]) return f[dep][cur][mod];
int ed = eq ? a[dep] : 9;
ll res = 0;
for (int i = 0; i <= ed; ++i) res += dp(eq and (i == ed), dep - 1, cur + i, (mod * 10 + i) % sum);
if (!eq) f[dep][cur][mod] = res;
return res;
}
ll work(ll n) {
a[0] = 0;
while (n) {
a[++a[0]] = n % 10;
n /= 10;
}
ll res = 0;
for (int i = 1; i <= a[0] * 9; ++i) {
sum = i;
memset(f, -1, sizeof f);
res += dp(1, a[0], 0, 0);
}
return res;
}
int main() {
ll l, r;
cin >> l >> r;
ll ans = work(r) - work(l - 1);
cout << ans << '\n';
return 0;
}
一些练习题
01背包：
- [NOIP2005 普及组] 采药
- Dima and Salad （01背包）
- [USACO07DEC]Charm Bracelet S (01背包)
- [NOIP2006 普及组] 开心的金明 （01背包）
- Fire （01背包）
- 最后一块石头的重量 II （01布尔背包）
- Cooking （01布尔背包）
- 异或和是质数的子集数
- 5 倍经验日
- haruki の覚醒め （01布尔背包）
- 严酷的训练
完全背包：
- 商店购物 Shopping Offers
- Piggy-Bank （完全背包）
- 零钱兑换
- [AHOI2001]质数和分解 （求方案数）
多重背包：
- 摆花 （多重背包）
- PolandBall and Gifts （贪心、多重背包）
- 飞扬的小鸟 （多重背包或完全背包）
二维费用背包：
区间dp：
- 狼群 （区间DP）
- [CQOI2007]涂色（区间DP）
优秀