动态规划模型例题
dp分析法
- 状态表示
- 集合描述：所有满足条件1、条件2、……的元素的集合（其中每个条件对应状态表示的每一维、元素意义对应求解的量）
- 集合属性：最大值，最小值，数量
- 目标：在集合定义下，答案是什么
- 状态计算（集合的划分：将当前要求的状态进行划分为若干个真子集（抓住定义），原则是不漏、求数量要求不重复，由前面得到的状态值，算出当前状态值）
- 状态转移方程
- 边界（最初子问题的解）（从状态表示出发）
技巧：
- 如果状态转移方程中有i - 1，那数组下标一般从1开始，否则一般从0开始
- 时间复杂度：状态数量 * 转移一次的计算量
- 划分方式：
- 以最后一步的所有选择划分
背包问题
01背包
模型：
有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
特点：每件物品仅有一件，可以选择放或不放。
// 边界：f[0][0~v] = 0
// c[]存物体的体积, w[]存物体的价值
// 二维数组
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= v; j ++ )
{
f[i][j] = f[i - 1][j];
if (j >= c[i])
f[i][j] = max(f[i][j], f[i - 1][j - c[i]] + w[i]);
}
cout << f[n][v]; // 答案
// 一维数组
// 第i轮循环求的是从前i个物品中挑，总体积不大于0~v的选法的最大价值，结果存在f[]中。所以在第i轮循环开始时，f[]中存的是从前i-1个物品中挑选，总体积不大于0~v的选法的最大价值。由于总体积在0~c[i]-1的选法的最大价值不变，所以只需要更新总体积c[i]~v的选法的最大价值即可。又因为这一轮f[j]的更新要用到上一轮f[j - c[i]]的值，所以j要从最大值v开始递减到c[i], 保证在更新f[j]时f[j - v[i]]还是上一轮的结果。
for (int i = 1; i <= n; i ++ )
for (int j = v; j >= c[i]; j -- )
f[j] = max(f[j], f[j - c[i]] + w[i]);
cout << f[v];
完全背包
模型：
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
特点：每件物品有无限个
完全背包状态转移方程的另一种理解：
分类：
- 不选i，那就是在前i - 1个中选，总体积不超过j。
f[i - 1][j] - 选了i，那就一定选了一个i，总体积剩下j - v[i]，由于i有无限个，可以继续选，所以相当于选了一个i后再在前i个中选，总体积不超过j - v[i]。
f[i][j - v[i]] + w
以上两种划分不重不漏：f[i][j] = f[i - 1][j] + f[i][j - v[i]] + w
// 朴素做法
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]);
// 二维数组
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];
// 一维数组
// 与01背包不同的是，对于总体积不大于v[i]~m的选法的最大值是用这一轮的f[j - v[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];
多重背包
模型：
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
特点：每件物品有限个，第i种物品有n[i]个
朴素做法类似于完全背包，枚举第i个物品选0~s[i]个，状态转移方程：
f[i][j] = max(f[i - k * v[i]] + k * w[i]), k = 0, 1,.., s[i]
// 朴素做法
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; 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]);
cout << f[n][m];
二进制优化：将每个s[i] 分解成1, 2, 4, 8, ..., 2 ^ k, c，其中2 ^ (k + 1) < s[i], c = s[i] - 2^(k + 1) - 1，保证1~s[i]中的任何一个数可以由这些数组合出来，且这些数的总和刚好是s[i]。这样的话，我们就可以把s[i]件物品分别打包成1件, 2件, ..., c件，每一包就看成一个体积为k * v[i], 价值为k * w[i]的物品包，每个物品包只能选一次，转化成了01背包问题。将所有的物品包用01背包的方法来选，得到的结果与朴素做法相同。
int w[N], v[N], f[M];
int cnt, n, m;
while (n -- )
{
int a, b, s;
scanf("%d%d%d", &a, &b, &s);
int k = 1;
while (k <= s)
{
cnt ++ ;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if (s) cnt ++ , v[cnt] = s * a, w[cnt] = s * b;
}
for (int i = 1; i <= cnt; 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件物品的体积是v[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
特点：物品分组，每一组里最多选一件
// 二维
int n, m, v[N][N], w[N][N], s[N];
int f[N][N];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
f[i][j] = f[i - 1][j];
for (int k = 1; k <= s[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];
// 一维
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= 0; 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算法体现为“作用在线性空间上的递推”，从一个或多个边界点开始有方向地向整个状态空间转移、拓展，最后每个状态上都保留了以自身为目标的子问题的最优解。
例如：背包问题中状态空间是一个二维矩阵，状态的值是1行1行算出来的。
数字三角形
初始化int为负无穷的方法:
0xcf ：-8e8 (推荐)
0x8f：-1.8e9
0x9f：-1.6e9
// 自顶向下
memset(f, 0xcf, sizeof f); // 初始化int为负无穷，每个是-8e8
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], f[i - 1][j]) + a[i][j];
int ans = -inf; // 目标
for (int i = 1; i <= n; i ++ ) ans = max(ans, f[n][i]);
cout << ans;
// 自下而上，从正下方和右下方
for (int i = n; i >= 1; i -- )
for (int j = i; j >= 1; j -- )
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];
cout << f[1][1] << endl;
最长上升子序列（LIS)
题目：给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
分析：
- 朴素版本：\(O(n^2)\)
边界：f[i]初始值为1
目标：max{f[i]}, 1 <= i <= n
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j <= i - 1; j ++ )
if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) ans = max(ans, f[i]);
cout << ans;
法二：二分优化:\(O(nlogn)\)
最长公共子序列（LCS)
题目：给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
分析：
01包含于f[i - 1, j]，所以max{01} <= max{f[i -1, j]}，同理类推，状态转移方程：
f[i, j] = max{f[i - 1, j], f[i, j - 1], f[i - 1, j - 1] + 1}
目标：f[N, M] ；边界：f[0, 0] = 0
// 下标从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];
经验：涉及到两个字符串的状态表示可以用二维的f[i, j]，i控制第一个字符串，j控制第二个字符串。
区间DP
区间DP也属于线性DP中的一种，它以“区间长度”作为DP的“阶段”，使用两个坐标（区间的左、右端点）描述每个维度。在区间DP中，一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来。区间DP的初态一般就由长度为1的“元区间”构成。
石子合并
原题链接：282. 石子合并 - AcWing题库
目标：f[1][n]
状态计算：要合并[i, j]内的石堆，选定第k堆石子，先合并[i, k]和[k + 1, j]，最后再将这两堆合并，这种方式可以枚举合并[i, j]石堆的所有方法。状态转移方程：
f[i][j] = min(f[i][k] + f[k + 1][j] + s[j] - s[i - 1]), i<= k<= j-1
在区间DP中，一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来。所以区间的状态值应从小到大计算。
边界：f[i][i]= 0
for (int len = 2; len <= n; len ++ ) // len = 1时为0，不用算，区间长度从小到大
for (int i = 1; i + len - 1 <= n; i ++ ) // 枚举长度为len的区间的左端点
{
int l = i, r = len + i - 1; // 每个状态的左右端点
f[l][r] = 0x3f3f3f3f;
for (int k = l; k <= r - 1; k ++ )
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n] << endl;
计数类DP
要求集合划分不重不漏，属性是数量
数位统计DP
重点：分情况讨论
状态压缩DP
当前子问题的决策受到前面子问题的影响，但不是像线性DP一样只是简单地由前面的结果得到当前结果，这个影响是一个复杂的集合，我们将这个影响的k种情况，n个维度压缩在一个n位的K进制数里。那么[0, k ^ n - 1]的十进制整数就可以表示所有的影响了。
例如蒙德里安的梦想中：第i - 2列对第i - 1列的影响有两种情况：1. 第i - 2 列的横向小方块伸到了第i - 1列、 2. 第i - 2 列的横向小方块没有伸到了第i - 1列。并且有n行，即n个维度。所以我们把这个状态压缩到一个n位的2进制数中。[0, 2 ^ n - 1]就代表了第i - 2列的所有横向方块的摆法。
树形DP
记忆化搜索
可解的前提是状态空间是拓扑图，即不存在环
优点：可以更快地实现状态转移方程。
线性DP可以用循环，区间DP用记忆化搜索更好写。
标签：状态,背包,int,max,代码,模板,物品,动态,DP From： https://www.cnblogs.com/zhengzirui/p/16940214.html