知识点
知识点
- 动态规划的基本思想
- 动态规划问题的基本套路与步骤
- 0-1背包 & 完全背包 & 多重背包问题
- LCS & LIS
- 经典动态规划问题
动态规划基础
为什么使用动态规划算法
我们先回忆一下贪心问题。
贪心又称贪婪算法。是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而使得问题得到全局最优解。
它的特点：
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
贪心选择性质就是，该问题的每一步选择都在选择最优的情况下能够导致最终问题的答案也是最优。
其实贪心和动态规划的区别，你可以理解为一个是正推，一眼就能看出来最优子结构，依次按照最优子结构选择每个过程最优选择即可。
与之相反的动态规划是没办法按照题目的意思直接得到最优子结构的，详细请看下文叙说。
多阶段决策过程最优化问题
动态规划问题，是运筹学的一个分支，动态规划主要用于求解以时间划分阶段的动态过程的优化问题。
在实际生活中，动态规划问题与贪心问题相似，都是完成某一事件的过程可以划分成多个阶段。
但是与贪心不同的是动态规划的每个状态之间都会相互影响和相互干涉，也就是说在某一阶段做出的决策会影响整个事件的最终结果。
因为阶段是有先后的，所以某一阶段的选取受之前阶段的影响，他也会影响后面的阶段。
多阶段决策问题：
多阶段决策过程问题，就是一类在每一阶段都需要做出选择，且某一阶段的决策受前面所有阶段决策后的状态影响，他的决策又会影响后续的决策。
这样一类问题就是多阶段决策问题。
多阶段决策过程最优化问题：
在多阶段决策问题中，各个阶段采取的决策，通常与时间相关，但有时又与其他的线性的变量相关。
我们前面说到，某个阶段的决策是在前面做完了的决策引发的某一个状态开始进行决策的。
而现在做的决策又会使得状态进行转移，那么又影响了下次进行决策的状态。
所以说作决策时的状态是动态的，规划是解决最优化问题的方式，所以解决这种多阶段决策过程最优化的方法叫做动态规划。
动态规划中的术语解释（Dynamic rogramming）
- 阶段： 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同
- 状态： 述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的
- 决策： 根据题意要求，对每个阶段所做出的某种选择性操作
- 策略： 由每个阶段的决策组成的序列称为策略
- 状态转移方程： 用数学公式描述与阶段相关的状态间的演变规律
能采用动态规划求解的问题的性质
- 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
- 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
解题步骤
- 拆分问题
- 定义状态(并找出初状态)
- 找到状态转移
- 逆推找最优子结构
- 写出 DP 状态转移方程。
一般的模型方法
- 递归搜索法
- 记忆化搜索(记忆化暴力)
- 递推式法
经典例题数塔问题
我们先来回顾一下我们之前讲过的数塔问题：
题目描述:
如图数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
- 一步可沿左斜线向下或右斜线向下走；
- 三角形行数小于等于 100；
- 三角形中的数字为 0，1，…，99；
测试数据通过键盘逐行输入。
如上例数据应以样例所示格式输入。
样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30
运行限制:
- 最大运行时间：1s
- 最大运行内存：128M
题目分析:
- 定义状态 假设 dp[i][j] 为处理 a[i][j] 后能达到的最大值。
- 找出状态转移dp[i][j]怎么转移呢？按照题意他有两条路径可以转移dp[i+1][j]=dp[i][j]+a[i+1][j] 向下走dp[i+1][j+1]=dp[i][j]+a[i+1][j+1] 向右下走我们有办法知道这两条路径哪条更优吗？不能！因为通向了两个不同的决策过程。为什么贪心可以知道，因为贪心处理完之后通向的是同一个决策过程，这里dp[i+1][j]和dp[i+1][j+1]明显他们两个所能达到的状态是完全不同的，这就是动态规划和贪心的不同之处。那我们怎样处理呢，我们要做的就是达到同一个状态我们才能够判断那个是最优的，这就是最优子结构。
- 逆推找最优子结构虽然我们进行了逆推，但是实际上不是因为我们逆推做了什么，只是因为我们找最优子结构的过程中恰好做了逆推的过程。我们要找最优子结构，我们刚才说了，要找到达同一状态的转移才能比较。那我们就考虑什么状态能够转移得到 dp[i][j]，这时候我们直接看也能看出来是这两条路径 dp[i+1][j]+a[i][j],dp[i+1][j+1]+a[i][j]。
- 写出状态转移方程
dp[i][j] = max{dp[i+1][j]+a[i][j],dp[i+1][j+1]+a[i][j]}
空间优化，已知 dp[i][j] 的值只会被覆盖前使用一次，所以可以合并 dp[i][j] 和 a[i][j] 那么就变成了
a[i][j] = max{a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]}
逆推到出发点 a[1][1] 为题目所求答案，即第一层到第 N 层的最大值。
答案解析：
#include <iostream>
using namespace std;
int main()
{
int n; // n层
int a[101][101]; // 路径矩阵
cin >> n;
// 输入数字三角形的值
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
cin >> a[i][j]; // 输入原始数据
}
}
// 递推开始
for (int i = n - 1; i >= 1; i--) // 从最后一层逆推
{
for (int j = 1; j <= i; j++)
{
if (a[i + 1][j] >= a[i + 1][j + 1])
a[i][j] += a[i + 1][j]; // 路径选择
else
a[i][j] += a[i + 1][j + 1];
}
}
cout << a[1][1] << endl;
}
其实我们在讲这道题目中所用到的思想就是动态规划。
我们换种方式在理解一遍。
在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。
从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。
同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。
这样一层一层推下去，直到倒数第二层时就非常明了。
所以第一步对第五层的 8 个数据，做如下四次决策：
- 如果经过第四层 2，则在第五层的 4 和 5 中，决策选择的肯定是 19
- 如果经过第四层 7，则在第五层的 5 和 2 中，决策选择的肯定是 10
- 如果经过第四层第一个 4，则在第五层的 2 和 6 中，决策选择的肯定是 6
- 如果经过第四层第二个 4，则在第五层的 6 和 5 中肯定是 6
经过一次决策，问题降了一阶。5 层数塔问题转换成 4 层数塔问题，经过如此的决策，就将原来问题转换为一阶数塔问题。
于是我们可以用我们上面的递推求解。
这就是递推式法模型。
我们通过这道简单的例题，大家首先要去找感觉，去分解问题的状态，去找决策，去找状态转移，而笔者认为动态规划问题，感觉是最重要的。
有的人 10 道题就能找到感觉，有的人 100 道题也找不到感觉。
Practice1
游戏中的学问
难度: 简单 标签: DP, JSOI, 2013
题目链接：https://www.lanqiao.cn/problems/1436/learning/
答案解析：
题目是说随即的拉住右手，共计 N 个人形成 k 个独立环的可能的情况有多少种。
我们举个例子，A B C 三个人：
A 的左手是 C A 的右手是 B B 的左手是 A B 的右手是 C C 的左手是 B C 的右手是 A
A 的左手是 B A 的右手是 C B 的左手是 C B 的右手是 A C 的左手是 A C 的右手是 B
这两种是不同的。
最后对 P 取模。
这道题目可以说是记忆化搜索，也可以说是递推法模型。
定义状态：
我们设 dp{i,j} 是 i 个人组成 j 个圈有多少种情况的状态
找初始状态：
由于最少是三个人围成 1 个圈
所以 dp{3,1}=2
找状态转移：
我们考虑 dp{4,1} 的时候： 由于一开始三个人之间共计 3 个空位置，它可以见缝插针，所以就有 3×dp{3,1}，dp{4,1}=3×dp{3,1}
接着考虑 dp{x+1,y}和 dp{x,y} 的关系：
假设 X 个人分成了 y 个环后每个环得人数是 X1 X2 … Xy
对于第一个环 X1 来说共有 X1 个空
对于第二个环 X2 来说共有 X2 个空
共计 X1+X2+…+Xy=X
所以共有 X 个空，那么第 X+1 个人就用 X 种选择可以做。
所以 dp{x+1,y}=x×dp{x,y}，即 dp{i,j}=(i-1)*dp{i-1,j}
考虑 dp{6,1}和 dp{6,2} ：
大家考虑以下我们划分阶段得方式是什么，是圈数吗？
如果是圈数，我们发现好像 {6，1}和{6，2}两个状态之间没有什么关系？
单纯的圈数不存在关系。
我们思考一下，至少需要 3 个人才能组成一个圈。
所以第 i 个人加入时，要在前 i-1 个人中 抽出两个人才能组成一个新圈。
所以原本的 dp{i-1,j}的状态就变成了，dp{i-3,j}了。
由于是从 i-1 个人中抽出 2 个人所以，共计
的抽取方式，3 个人我们已知能组成两种方案。
根据组合数求方案数的方式
所以 dp{i,j+1}=dp{i-3,j}×(i-1)×(i-2)
即 dp{i,j}=dp{i-3,j-1}×(i-1)×(i-2)
就此我们得到状态转移方程
- dp{i,j}=dp{i-1,j}×(i-1)
- dp{i,j}=dp{i-3,j-1}×(i-1)×(i-2)
除此之外，我们还有要考虑的情况，即建不建立新圈都是 dp{i,j}的情况，所以这里不是等于，而是求和:
dp{i,j}=dp{i-1,j}×(i-1)
dp{i,j}=dp{i,j}+dp{i-3,j-1}×(i-1)×(i-2)
比如：
dp{7,2}可以由 dp{6,2}转移而来
dp{7,2}也可以由 dp{4,1}转移而来
为什么这两种情况没有重叠，而是绝对异构的：
dp{6,2}由 dp{3,1}转移而来
dp{4,1}由 dp{3,1}转移而来
dp{4,1}中 1-4 号是在同一个圈内的。
dp{6,2}中 两个圈中的任意 3 个在一个圈内
不可能出现 1-4 在一个圈里的这种情况。
所以推导 dp{i,j}
dp{i,j}由 dp{i-i,j}转移而来 dp{i,j}也可以由 dp{i-3,j-1} 转移而来
dp{i-i,j}可以由 dp{i-2,j}或者 dp{i-4,j-1} dp{i-3,j-1}可以由 dp{i-4,j-1}或者 dp{i-6,j-2}
最终还是会到 3,1。
所以通过 3，通过两种方式走向了完全不同的方向。
至此我们轻松写出代码。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
LL DP[3100][3100], mod;
int n, k;
int main()
{
cin >> n >> k >> mod;
DP[3][1] = 2;
for (int i = 4; i <= n; i++)
{
for (int j = 1; 3 * j <= i && j <= k; j++)
{
DP[i][j] = DP[i - 1][j] * (i - 1) % mod;
DP[i][j] = (DP[i][j] + DP[i - 3][j - 1] * (i - 1) * (i - 2)) % mod;
}
}
cout << DP[n][k];
return 0;
}
Practice2
跳跃
难度: 简单 标签: 动态规划, 搜索, 2021, 模拟赛
题目链接：https://www.lanqiao.cn/problems/553/learning/
答案解析：
由于这道题目数据较弱，大家可以使用搜索把所有情况都搜索到，每次到终点就保存最大值，知道遍历完所有的情况，然后输出最大值。
大家一定要写一遍 DFS 然后在看后边的 DP ,有时动态规划要从状态出发，有时动态规划又可以看成暴力搜索的剪枝。
我们先看一下搜索的解法：
因为只能向右下方移动，不存再走回头路的情况，所以不需要设置 Vis 数组。
#include <iostream>
#define MAX 105
using namespace std;
int n, m, sum = -0x3f3f3f3f;
int map[MAX][MAX];
int nextt[9][2] = {{0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {1, 1}, {1, 2}, {2, 1}};
void dfs(int x, int y, int value)
{
value += map[x][y];
if (x == n && y == m)
{
sum = max(sum, value);
return;
}
for (int i = 0; i < 9; i++)
{
int tx = x + nextt[i][0];
int ty = y + nextt[i][1];
if (tx <= n && ty <= m)
dfs(tx, ty, value);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
dfs(1, 1, 0);
cout << sum;
return 0;
}
我们再来看一下 DP 怎么解这个问题。
定义状态：
我们设 dp{i,j} 当走到第 i 行第 j 列的值。
找初始状态：
dp{1,1}
找状态转移：
对于 dp{i,j} 会有 9 种不同的状态转移，我们很难知道当前的选择去怎样影响后续的值，这就是上边的搜索问题，我们难以找到一种 DP 思路去求解这个问题，但是我们反向考虑，既然 dp{i,j} 会有 9 种转移方式，那么当这 9 种状态的值为从这九种状态到达终点的最优解（最大值）时，那么我们就能轻易得到 dp{i,j}的最大值为这九种最优解的最大值。
继续消解子问题，那么我们得到这 9 种最优子状态，继续根据同样的原理得到这 9 种最优的子状态的最优子状态。
持续消解，发现只有到了 dp{n,m} 采用终止，这就是一个递归的过程。
这个过程是正推，根据递归写出递推来就变成了逆推，其实并不是根据动态规划写出来的逆推式，而是用正推递归变递推变来的，当然有的同学一眼看出来，那是非常优秀的。
这个题目数据量较小，用递归写不会爆，大家可以根据我的伪代码写写试试。
正推也是可以写出递推式，大家有兴趣可以尝试下。
#include <iostream>
#define MAX 105
using namespace std;
int n, m, sum = -0x3f3f3f3f;
int map[MAX][MAX];
int nextt[9][2] = {{0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {1, 1}, {1, 2}, {2, 1}};
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
for (int i = n; i >= 1; i--)
{
for (int j = m; j >= 1; j--)
{
if (i == n && j == m)
continue;
int maxTemp = -0x3f3f3f3f;
for (int k = 0; k < 9; k++)
{
int tx = i + nextt[k][0];
int ty = j + nextt[k][1];
if (tx > n || ty > m)
continue;
maxTemp = max(maxTemp, map[tx][ty]);
}
map[i][j] += maxTemp;
}
}
// for (int i = 1; i <= n; i++){
// for (int j = 1; j <= m; j++)
// cout << map[i][j]<<" ";
// cout<<endl;
// }
cout << map[1][1];
return 0;
}
背包问题
背包问题，是比赛中常考的问题，也是动态规划入门的问题，其实动态规划并没有套路，只是这类问题有着明确的特点，如果你做的题足够多的话，你会发现很多问题都会有模板。背包问题基本都是不可拆分背包，因为可拆分背包是贪心去求解的问题。我们今天讲三种背包的基本模型：
1. 0-1 背包、
2. 完全背包、
3. 多重背包问题。
0-1 背包问题
0-1 背包是背包问题的入门的问题。但是背包问题的模板也是最简单的。
0-1 背包的问题是什么呢？
其问题的简单表述为，有 N 件物品，每件物品只有一件。每个物品都有一个价值_wi_，每件物品都有一个占一个部分空间_ci_,已知你的背包共计可承重 C(Contains),现在让你求你的背包最多装得下多少_wMax_，即求你背包中物品的最大价值_wMax_。
对于这个问题我们有以下模板:
1.定义变量并输入
// 定义V,W用于保存价值和质量
#define Maxn 5000
int c[Maxn], w[Maxn];
int C;
// 输入
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> c[i] >> w[i];
}
cin >> C;
// 创建动态规划数组
int dp[Maxn];
2.执行算法
我们先去找到状态转移方程
dp[i][j]=max(dp[i][j],dp[i−1]j−c[i]]+w[i])
含义，选到第 i 件物品，且背包现在重量为 j。
那么考虑这个状态会由什么状态转移而来，肯定是选到第 i-1 件的时候。
如果选了第 i 件，那么就是由 dp[i−1]j−c[i]]转移而来。
如果不选第 i 件，那么就是由 dp[i][j]转移而来。
那么已知 dp[i−1]j−c[i]]和 dp[i][j]都为各自最优的状态，那我们直接取最优状态即可。
for(int i=0;i<n;i++)
{
for(int j=0;j<=C;j++)
{
if(j>=c[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]]+w[i]);
}
}
空间优化：
因为状态转移每次只与上一层有关，所以用一个一维数组就可以。
为什么从大到小遍历， 看 dp[j]=dp[j-c[i]]+w[i]这一状态转移，是根据小的改大的，如果先把小的改了，那小的还会被用到，数据就不对了，所以从小到大。
for(int i=0;i<n;i++) //遍历每一件物品
for(int j=C;j>=c[i];j--)
//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解;
dp[j]=max(dp[j-c[i]]+w[i],dp[j]);
初始化细节：
- 装满 dp[0]=0，其余赋值-INF；
- 不装满全初始化为 0；
//装满
memset(dp, 0, sizeof(dp));
dp[0]=0;
//不装满
memset(dp, -0x3f, sizeof(dp));
Practice
**题目描述: **小明有一个容量为 V的背包。 这天他去商场购物，商场一共有 N 件物品，第 i 件物品的体积为 w ，价值为 v，每种物品都只有一个。 小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述:
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。
样例:
5 20
1 6
2 5
3 8
5 15
3 3
37
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
#include <iostream>
#include <cstring>
using namespace std;
#define Maxn 5000
int c[Maxn], w[Maxn];
int dp[Maxn];
int C;
// 输入
int n;
int main() {
cin >> n;
cin >> C;
for (int i = 0; i < n; i++) {
cin >> c[i] >> w[i];
}
int dp[Maxn];
memset(dp, 0, sizeof(dp)); //不装满
//创建动态规划数组
for (int i = 0; i < n; i++) //遍历每一件物品
{
for (int j = C; j >= c[i]; j--)
//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解;
dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}
cout << dp[C] << endl;
}
完全背包问题
完全背包是背包问题的入门的问题。
根据 0-1 背包写出模板也是很简单的。
完全背包的问题是什么呢？
其问题的简单表述为，有 N 件物品，每件物品有无数件。每个物品都有一个价值_wi_，每件物品都有一个占一个部分空间_ci_,已知你的背包共计可承重 C(Contains),现在让你求你的背包最多装得下多少_wMax_，即求你背包中物品的最大价值_wMax_。
对于这个问题我们有以下模板:
1.定义变量并输入
参考 0-1 背包。
2.执行算法
我们先去找到状态转移方程
dp[i][j]=max(dp[i][j],dp[i]j−c[i]]+w[i])
含义，选到第 i 件物品，且背包现在重量为 j。
那么考虑这个状态会由什么状态转移而来，肯定是选到第 i-1 件的时候,或者选了若干次第 i 件。
如果不选第 i 种，那么就是由 dp[i-1][j] 转移而来。
如果选了第 i 件，那么就是由 dp[i−1]j−c[i]] 转移而来。
或者在某一刻，不在选第 i 件了，那么就是有 dp[i][j] 转移而来。
那么已知 dp[i]j−c[i]] 和 dp[i][j] 都为各自最优的状态，那我们直接取最优状态即可。
for(int i=0;i<n;i++){
for(int j=0;j<=C;j++){
dp[i][j]=dp[i-1][j];
if(j>=c[i]) dp[i][j]=max(dp[i][j],dp[i][j-c[i]]+w[i]);
}
}
cout<<dp[n][C]<<endl;
空间优化：
因为状态转移每次只与上一层有关，所以用一个一维数组就可以。
为什么从小到大遍历， 看 dp[j]=dp[j-c[i]]+w[i]这一状态转移，是根据小的改大的，而此时的含义为选了 x 件后的容量与质量，跟 01 背包类似，但含义不同，处理方式上也有本质区别，处理完一件后在处理下件。
for(int i=0;i<n;i++) //遍历每一件物品
for(int j=c[i];j<=C;j++)
//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解;
dp[j]=max(dp[j-c[i]]+w[i],dp[j]);
初始化细节：
与 0 - 1 背包相同。
- 装满 dp[0]=0，其余赋值-INF；
- 不装满全初始化为 0；
Practice
题目描述:
小明有一个容量为 V的背包。 这天他去商场购物，商场一共有 N 件物品，第 i 件物品的体积为 w ，价值为 v，每种物品都有无限多个。 小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述:
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。
样例:
5 20
1 6
2 5
3 8
5 15
3 3
120
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
#include <iostream>
#include <cstring>
using namespace std;
#define Maxn 5000
int c[Maxn], w[Maxn];
int dp[Maxn];
int C;
// 输入
int n;
int main() {
cin >> n;
cin >> C;
for (int i = 0; i < n; i++) {
cin >> c[i] >> w[i];
}
int dp[Maxn];
memset(dp, 0, sizeof(dp)); //不装满
//创建动态规划数组
for (int i = 0; i < n; i++) //遍历每一件物品
{
for(int j=c[i];j<=C;j++)
//遍历背包容量，表示在上一层的基础上，容量为J时，第i件物品装或不装的最优解;
dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}
cout << dp[C] << endl;
}
多重背包
根据 0-1 背包写出模板也是很简单的。
多重背包的问题是什么呢？
其问题的简单表述为，有 N 件物品，每件物品有_si_件。每个物品都有一个价值_wi_，每件物品都有一个占一个部分空间_ci_,已知你的背包共计可承重 C(Contains),现在让你求你的背包最多装得下多少_wMax_，即求你背包中物品的最大价值_wMax_。
对于这个问题我们有以下模板:
1.定义变量并输入
参考 0-1 背包。
2.执行算法
这次我们直接空间优化，不再讲解二维做法：
多重背包是可以不选，也可以选 1 个，可以选多个，而 0-1 背包只能选 0 个或者 1 个。
那就直接把种物品分开，即可比如：
每个盘子 3 块钱，我有 2 个。每双筷子 1 块钱，我有 10 双，每对刀叉 3 块钱，我有 3 个。
那么我就可以拆成，有 2 个三块的盘子，每个可以选也可以不选，就变成了 0-1 背包。
也就是说，对于每种是可以选多个，那就直接拆分成独立的个体就可以了。
for(int i=0;i<n;i++)
//遍历每一个物品
for(int j=0;j<=s[i];j++)
//遍历物品的数量
for(int k=C;k>=c[i];k--)
//当做01背包来处理
{
//取01背包情况的dp[k]和dp[k-c[i]]+w[i]的最大值
dp[k]=max( dp[k],dp[k-c[i]]+w[i] );
}
不顾这样做大概率会超时，我们换一种理解方式：
01 背包是选或不选 ：
dp[j]=max(dp[j],dp[j-v[i]]+w[i])
多重背包是选 0 个，1 个，2 个…s[i]个
即 dp[j]=max(dp[j],dp[j - v[i] _ k]+w[i] _ k)
k=1,2,3,…s[i]
这两种本质原理没有差别，只是在于循环剪枝上，后者优于前者。
初始化细节：
与 0 - 1 背包相同。
- 装满 dp[0]=0，其余赋值-INF；
- 不装满全初始化为 0；
Practice
题目描述:
小明有一个容量为 V的背包。 这天他去商场购物，商场一共有 N 件物品，第 i 件物品的体积为 w ，价值为 v，每种物品都有s个。 小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述:
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 3 个正整数 w,v，s,表示物品的体积、价值和数量。
样例:
3 30
1 2 3
4 5 6
7 8 9
39
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
#include <iostream>
#include <cstring>
using namespace std;
#define Maxn 5000
int c[Maxn], w[Maxn], s[Maxn];
int dp[Maxn];
int C;
// 输入
int n;
int main() {
cin >> n;
cin >> C;
for (int i = 0; i < n; i++) {
cin >> c[i] >> w[i] >> s[i];
}
int dp[Maxn];
memset(dp, 0, sizeof(dp)); //不装满
//创建动态规划数组
for (int i = 0; i < n; i++)
//遍历每一个物品
{
for(int j=C;j>=c[i];j--)
{
for(int k=1;k<=s[i] && j>=k*c[i];k++)
//遍历物品的数量
dp[j]=max(dp[j],dp[j-k*c[i]]+w[i]*k);
}
}
cout << dp[C] << endl;
}
LIS 和 LCS
我们上节课讲了，动态规划中的背包问题，背包问题，是比赛中常考的问题，也是动态规划入门的问题。今天们要说的是另外比较有套路的两种问题。在说一遍，其实动态规划并没有套路，只是这类问题有着明确的特点，如果你做的题足够多的话，你会发现很多问题都会有模板。
我们今天讲最长公共子序列 LCS，最长上升子序列 LIS。
最长公共子序列 LCS
首先我们先说明一下什么是子序列。
子序列：
在原来序列中找出一部分组成的序列,中间不必连续。
子串与子序列的区别就是，子串必须连续，子序列不必连续，所以子串一定是子序列，子序列不一定是子串。
如 “ABCSEFGS” 的子序列可以为：
ABSGS ACSEGS 等
对于这个问题我们有以下模板:
1.定义变量并输入
#include <iostream>
#include <cstring>
using namespace std;
#define Maxn 5000
//定义最大长度
int dp[Maxn][Maxn];
//DP 辅助数组
string s[Maxn][Maxn];
string a,b;
int main()
{
cin >> a >> b;
memset(dp, 0, sizeof(dp));
}
2.执行算法
我们先去找到状态转移方程
① 当 i=0 或者 j=0 时：
dp[i][j]=0
显而易见，这是两个起始条件，在满足这个条件的时候，子序列的长度为 0。
② 当 i,j > 0 且 a[i]=b[j] 时：
dp[i,j]=dp[i-1,j-1]+1
上一个状态是 dp[i-1,j-1],当 a[i]=b[j]的时候，子序列的长度+1,下标 i、j 同时后移,此时的状态转移到了 dp[i,j]
③ 当 i,j>0 且 a[i]≠b[j] 时：
上一个状态是 dp[i-1,j-1]，不对！！！
因为两个都相同的时候，a 的下标 i 和 b 的下标 j 都要向后移动，所以他是由 dp[i-1,j-1]转移而来。
不同的时候，要么 i 向后移动，要么 j 向后移动，自己考虑一下，你在自己手动求子序列的时候，是不是也是这么做的。
所以它是由 dp[i-1,j] 或者 dp[i,j-1] 转移而来。
因为 dp[i,j] 在 a[i]≠b[j] 时 只能由 dp[i-1,j] 或者 dp[i,j-1]，因为动态规划问题无后效性，所以我们认为之前的选择不会影响我们后边的选择。所以为了求最长子序列，这里应该是:
dp[i,j]=max{dp[i-1,j] , dp[i,j-1] }
虽然最后结果确实是这样的，这里是我们在做动态规划问题的时候，经常遇到错误。
因为某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
这样才能采用动态规划，而不是动态规划问题没有后效性，我们想当然的以为这个题是动态规划然后用来无后效性。
只有在你证明不了或者无法分析，想赌一把的时候可以忽略，试一下。
但是要想使用动态规划，就必须证明子决策无后效性。
就比如在 a[i] 和 b[j] 这里的状态是 dp[i][j] 我们决策受什么影响，只受 a[i]和 b[j]之间的关系的影响，
a[i-x] 和 b[j-y] 是否相等，会影响我们现在的决策吗？
No，这就是无后效性，所以我们可以进行：
dp[i,j]=max{dp[i-1,j] , dp[i,j-1] }
这样的状态转移。
如果只求最长公共子序列的长度就可以这样保存，但是如果他让我们暑输出最长公共子序列我们该怎么处理。
只需要在转移时，把转移的决策保存下来，那么决策的集合就是我们最后所求的结果。
我们需要设置一个数组辅助记录。
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
{
if (a[i] == b[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1;
s[i + 1][j + 1] = s[i][j] + a[i];
}
else
{
if (dp[i + 1][j] > dp[i][j + 1])
{
dp[i + 1][j + 1] = dp[i + 1][j];
s[i + 1][j + 1] = s[i + 1][j];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
s[i + 1][j + 1] = s[i][j + 1];
}
}
}
cout << dp[a.size()][b.size()] << endl;
cout << s[a.size()][b.size()];
这样是通过空间换时间，占用内存较大，但速度相对较快，也可以使用下面的方法。
#include <iostream>
#include <cstring>
using namespace std;
#define Maxn 5000
// 定义最大长度
int dp[Maxn][Maxn];
// DP 辅助数组
int c[Maxn][Maxn];
string a, b;
void printAns(int i, int j)
{
if (i == -1 || j == -1)
return;
if (c[i][j] == 0)
{
printAns(i - 1, j - 1);
cout << a[i];
}
else if (c[i][j] == 1)
printAns(i, j - 1);
else
printAns(i - 1, j);
}
int main()
{
cin >> a >> b;
dp[0][0] = 0;
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
{
if (a[i] == b[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1;
c[i][j] = 0; // 代表相等
}
else
{
if (dp[i + 1][j] > dp[i][j + 1])
{
dp[i + 1][j + 1] = dp[i + 1][j];
c[i][j] = 1; // 代表不相等，从上面的不相等
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
c[i][j] = -1; // 代表不相等，从左面的不相等
}
}
}
cout << dp[a.size()][b.size()] << endl;
printAns(a.size() - 1, b.size() - 1);
cout << endl;
}
Practice：
题目描述:
给定一个长度为 N 数组 a 和一个长度为 M 的数组 b。
请你求出它们的最长公共子序列长度为多少。
输入描述:
输入第一行包含两个整数 N,M，分别表示数组 a 和 b 的长度。
第二行包含 N 个整数a1,a2,…,an。
第三行包含 M 个整数 b1,b2,…,bn。
1≤N,M≤103，1≤ai,bi≤10^9。
样例:
5 6
1 2 3 4 5
2 3 2 1 4 5
4
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
#include <iostream>
#include <cstring>
using namespace std;
#define Maxn 5000
//定义最大长度
int dp[Maxn][Maxn];
//DP 辅助数组
int a[Maxn],b[Maxn];
int main()
{
int n,m;
cin >> n >> m;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
cin>>b[i];
dp[0][0] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (a[i] == b[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else
{
dp[i + 1][j + 1]=max(dp[i + 1][j], dp[i][j + 1]);
}
}
cout << dp[n][m] << endl;
}
LIS 最长上升子序列
我们首先定义状态：
我们定义 dp[i]为以 a[i]结尾的最长上升子序列长度。
设置 j 为小于 i 的某一点，那么当 a[j] < a[i] 时，必然有，以 a[j] 结尾的最长上升子序列,现在能以 a[i] 结尾，并且长度 +1 。
因为 j < i 且 a[j] < a[i]，满足上升子序列的要求。
所以 dp[i] 的一条转移路径为 dp[i]=dp[j]+1
但是 j 是比 i 小的某一个值，所以转移到 dp[i] 这一状态的值很多，我们要选择最优状态。
所以 dp[i]的状态转移：
dp[i]=max(dp[j]+1,dp[i]);
那么当 a[j] > a[i] 时
此时肯定不满足上升子序列，所以 dp[i] 与 dp[j] 毫无关联。
由此我们可以写出 LIS 的算法部分。
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (a[j] < a[i])
{
dp[i] = max(dp[j] + 1, dp[i]);
}
}
}
Practice：
题****目描述:
小明是蓝桥王国的骑士，他喜欢不断突破自我。这天蓝桥国王给他安排了 NNN 个对手，他们的战力值分别为 a1,a2,…,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。请你算算小明最多会挑战多少名对手。
输入描述:
输入第一行包含一个整数 NNN，表示对手的个数。
第二行包含 NNN 个整数 a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an，分别表示对手的战力值。
1≤N≤3×10^5，1≤ai≤10^9
样例:
6
1 4 2 2 5 6
4
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
#include <bits/stdc++.h>
using namespace std;
//求最长升序子序列的长度，并输出
#define Maxn 300006
int a[Maxn];
int dp[Maxn];
int ans=1;
int main()
{
int m,k;
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
dp[i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[j]+1,dp[i]);
}
ans=max(ans,dp[i]);
}
}
cout<<ans<<endl;
}
各类DP
线性DP（普通DP）
线性 DP 是动态规划问题中的一类问题，指状态之间有线性关系的动态规划问题。这类问题不像是我们讲的背包等问题有固定的模板。少数常见的线性 DP 问题也有模板，比如我们讲的 LIS 和 LCS 问题。大部分还是需要根据题目进行推导，基本没有什么规律可循。大部分线性规划的问题，都需要自己首先定义状态，找到决策，推导状态转移方程。我们再讲解几个题目，让大家找找做最普遍 DP 问题的感觉。
Practice1：
题目描述:
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
输入描述:
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
其中有 ，两个字符串的长度均不超过 1000。
输出描述：
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
样例:
LanQiaoBei
LanTaiXiaoQiao
2
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
该题目是 LCS 的变形，由原来的一个字符或者一个数字的匹配变成了，一个单词的匹配。这个题目为先划分字符串变成基本的比较单位，然后再套用_LCS_ 模板即可完成这道题目。
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1005][1005];
string s1, s2;
string a[1005], b[1005];
int n=0, m=0;
int main()
{
cin >> s1 >> s2;
int d1 = s1.length(), d2 = s2.length();
for (int i = 0; i < d1;)
{
if (s1[i] >= 'A' && s1[i] <= 'Z')
{
a[n] += s1[i++];
while (s1[i] >= 'a' && s1[i] <= 'z')
{
a[n] += s1[i++];
}
}
n++;
}
for (int i = 0; i < d2;)
{
if (s2[i] >= 'A' && s2[i] <= 'Z')
{
b[m] += s2[i++];
while (s2[i] >= 'a' && s2[i] <= 'z')
{
b[m] += s2[i++];
}
}
m++;
}
dp[0][0] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (a[i] == b[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else
{
dp[i + 1][j + 1]=max(dp[i + 1][j], dp[i][j + 1]);
}
}
cout << dp[n][m] << endl;
}
Practice2：
题目描述:
N位同学站成一排，音乐老师要请其中的(N−K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK， 则他们的身高满足T1<…< Ti>Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述:
共二行。
第一行是一个整数N(2≤N≤100)，表示同学的总数。
第二行有n个整数，用空格分隔，第i个整数Ti(130≤Ti≤230)是第ii位同学的身高(厘米)。
输出描述:
一个整数，最少需要几位同学出列。
样例:
8
186 186 150 200 160 130 197 220
4
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
要使得出列最少，那么就要留下最多的，我们想到了_LIS_ ，但是_LIS_ 只能处理单调序列最长，所以并不能直接用。
我们看到，这里是两头低，中间高的一种情况。
在这种情况下，最多的话那么就是最高的那个人的左侧加上右侧最高。
到这，我们发现。
在中间那个人左侧，从左到右做了一遍 LIS 。
在那个人的右侧，从右到左的做了一遍 LIS 。
至此，我们好像找了策略。
通过枚举中间那个人，然后看他左侧的 LIS 和他右侧的 LIS 的值之和的大小，就能将这道题目解出。
#include <iostream>
#include <algorithm>
using namespace std;
int dp1[105],dp2[105],a[105],s[105];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp2[i]=1;
dp1[i]=1;
}//输入并赋初值
//预处理，从右往左LIS
for(int i=n-1;i>=1;i--)
{
for(int j=i+1;j<=n;j++)
{
if(a[i]>a[j]&&dp2[i]<=dp2[j]+1)
{
dp2[i]=dp2[j]+1;
}
}
}
//预处理，从左往右LIS
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>a[j]&&dp1[i]<=dp1[j]+1)
{
dp1[i]=dp1[j]+1;
}
}
}
int maxx=0;
for(int i=1;i<=n;i++)
{
s[i]=dp2[i]+dp1[i]-1;
//自己算了两次，所以-1
if(s[i]>maxx)
{
maxx=s[i];
}
}
cout<<n-maxx;//是求出列的人数
}
Practice3：
题目描述:
我们称一个字符串S包含字符串T是指T是S的一个子序列，即可以从字符串S中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与T完全一样。给定两个字符串S和T，请问最少修改S中的多少个字符，能使S包含T ?
输入描述:
输入两行，每行一个字符串。
第一行的字符串为s，
第二行的字符串为T。
两个字符串均非空而且只包含大写英文字母。
输出描述:
输出一个整数，表示答案。
样例:
ABCDEABCD
AABZ
3
运行限制:
-
最大运行时间：1s
-
最大运行内存：128M
答案解析：
这个题目是线性 DP 中比较经典的题目。这个类型就做编辑距离，可以通过 DFS 解决，也可以通过 DP 解决。DP 的时间复杂度低。
我们先来讲一下，编辑距离。
编辑距离为两个字符串，a 和 b 通过多少次变换，使得 a 变成 b。
我们可以做出 3 种操作。
- 删除操作，将 a[i] 从 a 中移除
- 插入操作，在 a[i] 后加上 b[j]
- 替换操作，将 a[i] 修改为 b[j]
编辑距离的状态转移类似 LCS ，但有有很大的差别。
初始状态，i=j=0，都在字符串的开头。
然后开始判断 a[i]=?b[j]
- 如果相同，那么就不需要修改，所以_dp_[i+1][j+1]=dp[i][j]所以在_a_[i−1]等于b[j−1]时，dp[i][j]这个状态由_dp_[i−1][j−1]转移而来。dp[i][j]=dp[i−1][j−1]
- 如果不同，那就需要进行三种可能的操作
- 修改操作：
a[i] 修改为 b[j]， 因为编辑了一次，所以+1
dp[i+1][j+1]=dp[i][j]+1
所以在_a_[i−1]不等于_b_[j−1]时, dp[i][j]这个状态由_dp_[i−1][j−1]转移而来。
dp[i][j]=dp[i−1][j−1]
- 删除操作，直接把 a[i] 删除，此时转移到 dp[i][j+1] ，因为 a[i] 被删除，但是下一个字符到了 a[i] 的位置，而对应比较的位置到了_b_[j+1]。
所以此时状态转移到了_dp_[i][j+1]
dp[i][j+1]=dp[i][j]+1
因为编辑了一次，所以+1
所以在_a_[i−1]不等于_b_[j−1]时，dp[i][j]就有可能通过_dp_[i−1][j]转移而来。
- 插入操作，在_a_[i]后添加一个_b_[j]，那么此时_a_[i+1]和_b_[j]对应，因为加了一个字符就变成了_a_[i+1],而且跟_b_[j]对应，那么下一个状态转移到了_dp_[i+1][j]
dp[i+1][j]=dp[i][j]+1
此时状态转移到了_dp_[i+1][j]=dp[i][j]+1
因为编辑了一次，所以+1
所以在_a_[i−1]不等于_b_[j−1]时，dp[i][j]就有可能通过_dp_[i][j−1]转移而来。
那么不同时，我们选择他们的最小值即可。
由此我们可以写出模板：
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
using namespace std;
#define INF 99999999
string s, t;
int dp[1010][1010];
void init(){
for (int i = 0; i <= s.size(); i++) dp[i][0] = 0;
for (int j = 1; j <= t.size(); j++) dp[0][j] = INF;
}
int main() {
cin >> s >> t;
init();
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
cout << dp[s.size()][t.size()];
return 0;
}
这道题目也比较简单，由于是包含关系，并不是相等关系，所以当 S 多余 T 是，不需要进行删除操作。
所以这个题目不考虑删除的那个状态转移即可。
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
using namespace std;
#define INF 99999999
string s, t;
int dp[1010][1010];
void init(){
for (int i = 0; i <= s.size(); i++) dp[i][0] = 0;
for (int j = 1; j <= t.size(); j++) dp[0][j] = INF;
}
int main() {
cin >> s >> t;
init();
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j]);
}
}
cout << dp[s.size()][t.size()];
return 0;
}
状压DP
状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态。
若集合大小不超过 N，集合中每个元素都是小于 K 的自然数，则我们可以把这个集合看作一个 N 位 K 进制数，以一个 [0,KN -1]之间的十进制整数的形式作为 DP 状态的一维。
这种把集合转化为整数记录在 DP 状态中的一类算法，就被称为状态压缩的动态规划算法。
动态规划的过程是随着“阶段”的增长,在每个状态维度上不断扩展的。
在任意时刻，已经求出最优解的状态与尚未求出最优解的状态在各维度上的数据集合是我们索要关注的，对于某些问题，我们需要在动态规划的“状态”中记录一个集合，保存这个数据集合的详细信息，以便进行状态转移。
所以简而言之，状压 DP 就是在使用状态压缩的情况表示状态的情况下的动态规划。
位运算
状态压缩的核心就是位运算,那我们详细学习一下位运算。
- & 运算按位与运算符 & 有 0 为 0，无 0 为 1 and 运算通常用于二进制取位操作， 例如一个数 and 1 的结果就是取二进制的最末位。 这可以用来判断一个整数的奇偶， 二进制的最末位为 0 表示该数为偶数， 最末位为 1 表示该数为奇数.
- | 运算 按位或运算符 | 有 1 为 1 无 1 为 0 or 运算通常用于二进制特定位上的无条件赋值， 例如一个数 or 1 的结果就是把二进制最末位强行变成 1。 如果需要把二进制最末位变成 0， 对这个数 or 1 之后再减一就可以了， 其实际意义就是把这个数强行变成最接近的偶数。
- ^ 运算异或运算符 ^ 相同为 0 不同为 1 xor 运算通常用于对二进制的特定一位进行取反操作， 因为异或可以这样定义： 0 和 1 异或 0 都不变， 异或 1 则取反。
- ~ 运算 ~ 运算的定义是把内存中的 0 和 1 全部取反。 使用 ~ 运算时要格外小心， 你需要注意整数类型有没有符号。
- << 运算 a << b 就表示把 a 转为二进制后左移 b 位 （ 在后面添 b 个 0）。相当于 a 乘以 2 的 b 次方（ 取整）。
-
运算 和 << 相似， a >> b 表示二进制右移 b 位（ 去掉末 b 位）， 相当于 a 除以 2 的 b 次方（ 取整）。
位运算的优先级与结合性
| 运算符 | 结合性 | | :--------------------------------------------------: | :---------------: | -------- | -------- | | [ ].()(方法调用) | 从左向右 | | ! ~ ++ – +(一元运算) -(一元运算) (强制类型转换) new | 从右向左 | | * / % | 从左向右 | | + - | 从左向右 | | << >> >>> | 从左向右 | | < ≤ >= > instanceof | 从左向右 | | == != | 从左向右 | | & | 从左向右 | | ^ | 从左向右 | | | | 从左向右 | | && | 从左向右 | | | | | 从左向右 | | ?: | 从右向左 | | = += -= *= /= %= &= | = ^= <≤ >>= >>>= | 从右往左 |
但是记不住没关系，多用()即可。
位运算常用功能
那我们学会了如何采用二进制来表示状态，然后我们就找点真题做一做体验一下。
Practice1：
砝码称重
题目大意
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 _W_1,_W_2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。
解题思路
转化一下题意，砝码可以放在天平俩边意味着砝码的重量可以为正贡献也可以为负贡献(加上这个重量或者减去这个重量)，或者没有贡献(这个砝码不放)。
50_pts_：
这题 50 分的数据 N 最大只有 15， 我们假设每个砝码有加、减、不放三种情况，用穷举法枚举的复杂度为 不带 log 的话完全可以通过 50 的数据！ 题目给出 N 个砝码总重不超过 100000 , 这个就是不带 log 的关键！平时我们去重或者标记都是 set 或者 map ,这道题带个 log 的复杂度大概率就会超时，这题完全可以用一个数组表示这个数有没有出现过 ，复杂度。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 50;
int vis[maxn];
int a[maxn];
int n;
void dfs(int sum, int i){
if(i == n){
if(sum >= 0) vis[sum] = 1;
return ;
}
dfs(sum + a[i], i + 1);
dfs(sum, i + 1);
dfs(sum - a[i], i + 1);
}
int main()
{
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i];
}
dfs(0, 0);
int ans = 0;
for(int i = 1;i < maxn;i++) if(vis[i]) ans++;
cout << ans << endl;
return 0;
}
100_pts_：
正解当然是动态规划呐！同样表示每个砝码的三种状态为加、减、不放，假设题目条件简化一下，只能放一边, 哦豁，你会发现这不就是个简单的背包嘛,每个物品选和不选,最最简单的动态规划 01 背包的问题呀。
现在考虑能放俩边的情况，我们能不能在放一边的情况下计算呢？
假设我们放一边的时候是 不放 和 加 的情况，那么我们跑完 01 背包以后怎么加上 减这种情况呢？
其实有个很巧妙的做法，就是把 不放和加 做完计算以后当成一种状态， 那么和减的情况当成 01 背包的俩种状态， 如果你这个砝码用的是加这个状态，那么减去就相当于不放， 如果上次计算的状态是不放，那么减就是减去这个砝码的重量，相当于放在天平的另一边，这样不存在重复合漏算的情况惹。
结尾：顺便提一下，如果你对 C++ 的 STL 库熟悉的话，可以用 bitset 这个简单粗暴的工具直接模拟！结尾附上代码,简单到超乎你的想象。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[100005];
ll w[105];
int main(){
ll n;
cin >> n;
for(ll i = 1;i <= n;i++){
cin >> w[i];
}
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(ll i = 1;i <= n;i++){
for(ll j = 100000;j >= w[i];j--){
dp[j] = max(dp[j], dp[j - w[i]]);
}
}
for(ll i = 1;i <= n;i++){
ll siz = 100000 - w[i];
for(ll j = 1;j <= siz;j++){
dp[j] = max(dp[j],dp[j + w[i]]);
}
}
ll ans = 0;
for(ll i = 1; i <= 100000;i++){
ans += dp[i];
}
cout << ans << endl;
return 0;
}
Practice2:
题目大意
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？
两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。
解题思路
状压 dp。
由于教学楼的个数很少，我们考虑用一个二进制位数等于 2121 的数来表示教学楼的访问状态。
对于该二进制数，如果它的第 i 位（二进制下）的值为 1，则表示当前状态下第 i 栋教学楼已经访问过一次了；若它的第 i 位（二进制下）的值为 0，则表示当前状态下第 i 栋教学楼还未访问。
于是可以定义 dp[i][j] 表示当前的状态为 i，最后走到的教学楼为 j的方案数。
那么转移方程为：
dp[i+1<<k][j]+=dp[i][j]
其中需满足对于状态 i，教学楼 k 并未访问过（即 (i>>k&1)=0） 且 j,k 之间存在路径。
最后答案为 \sum_{i=0}^{n}dp[(1<<21)-1][i]=881012367360，时间复杂度为。
（注意：别忘了开 long long)
# python 跑的相当慢，不过这是道填空题就无所谓了
import math
dp = [[0] * (22) for i in range(2100000)]
g = [[0 for i in range(22)] for i in range(22)]
n = 1 << 21
for i in range(1, 22):
for j in range(1, 22):
if math.gcd(i, j) == 1:
g[i - 1][j - 1] = g[j - 1][i - 1] = 1
dp[1][0] = 1
i = 1
while i < n:
for j in range(0, 21):
if (i >> j & 1) == 0:
continue
for k in range(0, 21):
if g[j][k] == 0 or (i >> k & 1) != 0:
continue
dp[(i + (1 << k))][k] += dp[i][j]
i += 1
res = 0
for i in range(0, 21):
res += dp[n - 1][i]
print(res)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1 << 22][22] , g[22][22];
signed main()
{
int n = 1 << 21;
for(int i = 1 ; i <= 21 ; i ++) for(int j = 1 ; j <= 21 ; j ++){
if(__gcd(i , j) == 1) g[i - 1][j - 1] = g[j - 1][i - 1] = 1;
}
dp[1][0] = 1;
for(int i = 1 ; i < n ; i ++){
for(int j = 0 ; j < 21 ; j ++){
if(!(i >> j & 1)) continue ;
for(int k = 0 ; k < 21 ; k ++) {
if(!g[j][k] || (i >> k & 1)) continue ;
dp[i + (1 << k)][k] += dp[i][j];
}
}
}
int res = 0;
for(int i = 0 ; i < 21 ; i ++) {
res += dp[n - 1][i];
}
cout << res << '\n';
return 0;
}
树状DP
故名思意，树形 DP 就是在树上做 DP 的算法。我们之前做的动态规划有两种方向即向前推和向后推，相应的树形 DP 也是有两个方向。
给定一棵有 N 个节点的树(通常是无根树，也就是有 N-1 条无向边)，我们可以任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。
在树上设计动态规划算法时，一般就以节点从深到浅(子树从小到大)的顺序作为 DP 的“阶段”DP 的状态表示中，第一维通常是节点编号(代表以该节点为根的子树)。
大多数时候我们采用递归的方式实现树形动态规划。对于每个节点 x，先递归在它的每个子节点上进行 DP，在回溯时，从子节点向节点 x 进行状态转移。
难点：
- 因为树形的状态转移不能直接表示，所以需要搜索，所以与之前接触的动态规划相比树形 DP 是记忆化搜索的处理方式。
- 状态表示和状态转移，以及所处理的细节，对于某个状态要考虑父节点，子树，兄弟节点。树形 DP 的套路相对比较好想，题目做的多了之后会发现，变得跟线性一样，还是找转移方程。
只讲这些抽象的定义不如讲一道真题。
Practice1:
题目大意
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
对于一棵有根二叉树 T，小蓝定义这棵树中结点的权值 W(T) 如下：空子树的权值为 0。如果一个结点 v 有左子树 L, 右子树 R，分别有 C(L) 和 C(R) 个结点，则：
W(v) = 1 + 2W(L) + 3W(R) + (C(L)) ^ 2 C(R)。
树的权值定义为树的根结点的权值。小蓝想知道，对于一棵有 2021 个结点的二叉树，树的权值最小可能是多少？
- 最大运行时间：1s
- 最大运行内存: 128M
解题思路
这道题是一道题填空题，我们考虑暴力枚举，我们可以使用递归找到最小的结果。不过使用递归的方法可能会出现爆栈或者时间太久。所以我们考虑用动态规划。然后转移方程式怎么来呢。其实题目都给我们了，直接拿来用就行。每次 dp 都找最小值，依次往后推，每次得到当有 i 个节点时的最小值。最后的最小结果会存在 dp[2021] 的位置。
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long dp[2025];
memset(dp, 0x3f3f3f, sizeof(dp));
//初始置为0
dp[0] = 0;
for(int i = 1; i <= 2021; i++){
for(int j = 0; j < i; j++){
//左边节点j个右边节点i - 1 - j个
dp[i] = min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - 1 - j] + j * j * (i - 1 - j));
}
}
cout << dp[2021];
return 0;
}
Practice2:
题目大意
对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。
换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
给定一棵包含 �N 个结点的多叉树，结点从 11 至 �N 编号，其中 11 号结点是根，每个结点的父结点的编号比自己的编号小。
请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。
注：只有根结点这一个结点的树高度为 00。
解题思路
如果一个结点的父亲有_cnt_ 个孩子，那么在我们构造的树上，这_cnt_ 个孩子一定是以孩子、父亲、父亲的父亲、父亲的父亲的父亲、⋯⋯ 的方式相连的。
定义 dp[i] 表示以 i 为根的子树的最大高度。
如果结点 u 有 k 个孩子，分别为 _v_1,_v_2,⋯,vk。已知这 k 个孩子必定相连在一起，我们设它们的顺序分别为 _v_1,_v_2,⋯,vk，那么它们对 u 的左子树高度的贡献就分别为 （dp[_v_1],dp[_v_2]+1,⋯,dp[vk]+k−1）。显然，要使孩子对 u 的贡献最大，就要把 dp 值越大的孩子放在越底层。
而对于右子树，我们是无需考虑的。因为对于结点 u 来说，它的右子树只受它的兄弟影响。我们设 u 的父亲为 far，它的兄弟分别有 u′,u′′,u′′′。
那么在不考虑左子树的情况下，无论 u,u′′,u′′′,u′′′′ 怎么摆放，它们之中右子树的最大值都是 4，即对 dp[far] 的贡献必定为 4。
我们重点要的是孩子对其父亲结点的贡献，已知孩子的摆放顺序（孩子的右子树高度）对父亲结点的贡献不会有影响，所以我们也无需再另外考虑右子树了。
最后的答案为 dp[1]，复杂度为 O(n)。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+ 10;
struct Edge{
int nex , to;
}edge[N << 1];
int head[N << 1] , TOT;
void add_edge(int u , int v){
edge[++ TOT].nex = head[u];
edge[TOT].to = v;
head[u] = TOT;
}
int n , v , dp[N];
vector<int>vec[N];
void dfs(int u , int far){
int ma = 0;
for(int i = head[u] ; i ; i = edge[i].nex){
int v = edge[i].to;
if(v == far) continue ;
dfs(v , u);
ma = max(dp[v] , ma);
}
dp[u] = ma + vec[u].size();
}
signed main()
{
cin >> n;
for(int i = 2 ; i <= n ; i ++){
cin >> v;
vec[v].push_back(i);
add_edge(i , v) , add_edge(v , i);
}
dfs(1 , 0);
cout << dp[1] << '\n';
return 0;
}
数位DP
数位统计 DP 是与数字相关的一类计数问题。在这类题目中，一般给定一些限制条件，求满足限制条件的第 K 小的数是多少，或者求在区间 [L,R] 内有多少个满足限制条件的数。
所谓数位 DP，即在数位上进行动态规划。在这种方法中，数位指数字的个位、十位、百位和千位等位置，数的每一位就是数位！
数位 DP 的本质是一种取代暴力枚举的优化方法，它提供了一种有效的枚举方式，使其满足 DP 性质，并使用记忆化策略加速计算。
我们思考这样一道题目：
给定一个闭区间 [l,r]，让你求这个区间中满足 Check()条件的数的总数。正常枚举的方式如下：
int ans=0;
for(int i=l;i<=r;i++){
if(check(i))ans++;
}
当 r-l 超过 1e8 时，我们就可能超时了，那我们该怎么办呢？
引入数位动态规划。数位动态规划是一种将原有的暴力枚举方式转化为符合 DP 性质的方式。其特点是在进行求解前，首先进行动态规划预处理。
最朴素的计数就是从小到大开始依次加一。对于从小到大逐个加一的朴素计数方法，我们发现在位数较多的数中会产生许多重复的计算。例如，对于从 7000 到 7999、8000 到 8999 以及 9000 到 9999 这三个区间的计数，它们的某些部分是相同的，区别仅在于千位这一位的不同，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
我们来看：我们可以用 f(n) 表示 [0,n] 的所有满足条件的个数，那么对于[l,r] 我们就可以用 [l,r]⟺f(r)−f(l−1) ，相当于前缀和思想。
那么也就是说我们只要求出_f_(n)即可，我们可以预处理再求解 f(n)了。
将数拆分成位，从高位到低位开始枚举。我们可以视 N 为 n 位数，那么我们拆分 N:an、an−1…_a_1。 那么我们就可以开始分解建树，如下图所示。 
然后我们进行预处理，数位 DP 往往可以将左边分支的方案数预处理出来，预处理的具体方法根据题目需求而有所不同，有的需要使用 DP 进行处理，有的则需要运用组合数学或其他方法。通过预处理，可以大幅度降低时间复杂度，因为我们可以直接得到左侧分支的方案数，而无需继续枚举。然后，右侧分支继续向下枚举直到最低位。
有了答案数组_f_(n)，接下来的任务是统计答案。为了不重不漏地统计所有满足条件的数字，需要从高到低枚举整个数位，考虑每位可填哪些数字，利用_f_(n)数组进行统计。在这个过程中，可以采用记忆化搜索或循环迭代递推的方法。
Practice1:
题目大意
小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？
解题思路
一道裸的数位 dp 题，裸到即使你不会数位 dp，你也能写出来。
定义 dp[len][sum] 表示当前计算到了二进制数的第_len_ 位，前 len−1 位的 1 的个数为 sum，然后常规转移即可。
当然也有别的办法，比如设 n 对应的二进制数共有 cnt 位，那么答案就等于从 _cnt** 位中任选 **K** 位使它们的值为 1 的方案数减去这其中构造出来的比 **n_** 大的数**，即 ，X 表示从 cnt 位中任选 K 位使它们的值为 1 且数值大于 n 的方案数。此方法也很简单，这里就不多赘述。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , K , dp[66][66] , num[66];
int dfs(int len , int sum , bool limit){
if(!len) return sum == K;
if(~dp[len][sum] && !limit) return dp[len][sum];
int up = limit ? num[len] : 1 , res = 0;
for(int i = 0 ; i <= up ; i ++){
res += dfs(len - 1 , sum + (i == 1) , limit && i == up);
}
return dp[len][sum] = res;
}
int solve(int n){
memset(dp , -1 , sizeof(dp));
int len = 0;
while(n) num[++ len] = n % 2 , n /= 2;
return dfs(len , 0 , 1);
}
signed main(){
cin >> n >> K;
cout << solve(n) << '\n';
return 0;
}
Practice2:
C++/C 题解
给定 T 个数 _n_1,_n_2,⋯,nT，对每个 ni 请求出有多少组 a, b, c 满足：
- 1≤a,b,c≤ni；
- a⊕b⊕c=0，其中 ⊕ 表示二进制按位异或；
- 长度为 a,b,c 的三条边能组成一个三角形。
解题思路
- a⊕b⊕c=0 即 a⊕b=c、a⊕c=b、b⊕c=a。
- 长度为 a,b,c 的三条边能组成一个三角形即 a,b,c 三个数中最小的两个数的和大于最大的数。
10_pts_
直接暴力枚举 a,b,c 然后判断是否满足题目条件即可。
复杂度为 。
20_pts_
暴力枚举 a,b，那么 c=a⊕b，然后判断 c 是否不大于 n 以及是否满足题目条件即可。
复杂度为 。
50_pts_
设以 a 为 a,b,c 三个数中的最大值（b,c 大小关系不确定）的满足条件的方案数为 F，那么显然最终答案为 3×F。
如何求 F 呢？我们可以枚举 a 的值，这样首先就确定了一个数。然后我们只要再确定一个数，就可以确定三个数了（_b _⊕c=a）。
考虑二进制下的数位 dp。假设我们要确定的数为 b，则需要满足以下条件：
- b<a：令数位 dp 的上界为 a
- c<a： 要使 c<a，则 a 在 b 二进制下的最高位的值为 1。 比如 a=11100，则 b 可取的值有 100,1000,1000,101,110,⋯，而不可取的值有 1,10,11。
- b+c>a=b⊕c。 要使 b+c>b⊕c，则 b,c 在二进制下至少有一位的值都为 1。 比如 b=11100，则 c 可取的值有 100,101,110,111,1000⋯，不可取的值有 1,10,11。 c 是我们通过 a,b 计算来的，而要使 b,c 在二进制下至少有一位的值都为 1，则 a,b 必然在某位上满足 a 的值为 0，b 的值为 1。
结合以上条件，实现数位 dp 即可。
复杂度为。
60_pts_
和 50_pts_ 类似，我们进行一个预处理操作即可：先枚举 a（从枚举），然后对 b 进行数位 dp 得到对应的方案，再将其结果存储起来。这样在多组查询的时候，我们就能 得到答案了。
复杂度为。
100_pts_
对于 50_pts_，因为 a 的最大范围为 ，所以我们可以枚举 a，以此来确定一个数后再对另一个数进行数位 dp 得到答案。但是现在 a 的最大范围为 次方，显然枚举是不可能的了。不过既然 b 可以用数位 dp 处理，那 a 是不是也能用数位 dp 处理呢？
好吧这其实就是个数位 dp 的经典套路 — 同时处理多个数。
我们还是以 a 为最大值，先对其进行处理，仅有一个限制 a<n，我们将其上界定为 n 即可。
接下来考虑 b （此时 a 已确定）：
- 由于 b<a，所以我们需要将 b 的上界设为 a。
- c<a，处理同上。
- b+c>a=b⊕c，处理同上。
关于实现:
定义 dp[len][_limit_1][_limit_2][_ok_1][_ok_2]，为当前进行到二进制下的第 len 位;
a 是否达到上界( _limit_1=0 表示未到达，反之表示达到)；
b 是否达到上界(_limit_2=0 表示未到达，反之表示达到)；
是否满足 c<a（_ok_1=1 表示满足，反之表示未满足）；
是否满足 b+c>a=b⊕c（_ok_2=1 表示满足，反之表示未满足）;
那么转移的核心如下：
int up1 = limit1 ? num[len] : 1 , res = 0;
for(int i = 0 ; i <= up1 ; i ++){
int up2 = limit2 ? i : 1;
for(int j = 0 ; j <= up2 ; j ++){
if(!ok1 && !i && j) continue ;
res += dfs(len - 1 , limit1 && i == up1 , limit2 && j == up2 , ok1 || (j == i && j == 1) , ok2 || (j == 1 && j != i));
}
}
复杂度为 。
由于常数较大，请务必进行一些卡常处理！
#pragma GCC target ("avx2,fma")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
int n , dp[32][2][2][2][2] , num[32];
inline int dfs(int len , bool limit1 , bool limit2 , bool ok1 , bool ok2){
if(!len) return ok2 ? 1 : 0;
if(~dp[len][limit1][limit2][ok1][ok2]) return dp[len][limit1][limit2][ok1][ok2];
int up1 = limit1 ? num[len] : 1 , res = 0;
for(int i = 0 ; i <= up1 ; i ++){
int up2 = limit2 ? i : 1;
// 以下代码和上文所提的核心代码意义完全相同，只是拆开写了（拆开写程序跑的会快上一些）。
if(!ok1){
if(!i) res += dfs(len - 1 , limit1 && !up1 , limit2 && !up2 , 0 , 0);
else {
res += dfs(len - 1 , limit1 && up1 , limit2 && !up2 , 0 , 0);
if(up2 == 1) res += dfs(len - 1 , limit1 && up1 , limit2 , 1 , 0);
}
}
else{
if(!i) {
res += dfs(len - 1 , limit1 && !up1 , limit2 && !up2 , 1 , ok2);
if(up2 == 1) res += dfs(len - 1 , limit1 && !up1 , limit2 && up2 , 1 , 1);
}
else{
res += dfs(len - 1 , limit1 && up1 , limit2 && !up2 , 1 , ok2);
if(up2 == 1) res += dfs(len - 1 , limit1 && up1 , limit2 && up2 , 1 , ok2);
}
}
}
return dp[len][limit1][limit2][ok1][ok2] = res;
}
inline int solve(int n){
memset(dp , -1 , sizeof(dp));
int len = 0;
while(n) num[++ len] = n & 1 , n >>= 1;
return dfs(len , 1 , 1 , 0 , 0);
}
signed main(){
int T = 1;
read(T);
while(T --){
read(n);
Out(solve(n) * 3) , putchar('\n');
}
return 0;
}
Practice3:
好数之和
问题描述
一个整数如果包含连续的 2022 四个数字, 我们就称之为 “好数”。
例如 2022、52022、20223、7020224 都是好数, 而 2202、20022、2222 都不 是好数。
给定 L 和 R, 请你计算在 L 到 R 之间（包含 L 和 R ) 所有好数的和是多少?
解题思路
一道比较另类的数位dp问题，和常规的数位dp问题不同，这题不是求满足条件的数的个数，而是数的总和，所以我们在转移的时候要统计两个信息：满足条件的数的个数和这个数对答案的贡献，就将dp数组定义为结构体类型。这里暴力求解显然不可靠，所以我们就边转移边记录数对答案的贡献。
怎么确定数里面含有“2022”了，我们可以采取一种不算太聪明但是可行的方案：记录5个状态，last1,last2,last3，分别代表当前这个数位的前3,2,1位对应的数（如果前面不存在数，把它看成0），now代表当前这个数位对应的数，sta代表该数是否已经满足了条件，显然要让该数满足条件，就必须出现这样的情况：
用记忆化搜索，每次计算好的状态用数组记录下来，虽然是六维 dp，但其实开辟的空间大小只是 20×10×10×10×10×2=400000 这么大，不用担心会MLE。dp 数组状态定义：
分别表示当前的数位、该位的前3位对应的数、该位的前2位对应的数、该位的前1位对应的数、当前位对应的数、条件是否已经满足） 边界条件：（F代表当前函数的返回值） 
状态转移：
对任意一个数 x 执行一遍 solve 函数，求的是中 [0,x] 中含有“2022”的数的总和，而为了求区间[a,b] 的解，就用 b 求出的总和减去 a-1 求出的总和即可。
#include <bits/stdc++.h>
using namespace std;
int cnt[20];
long long ppow[22];
struct Point {
long long x, y;
Point() {}
Point(long long x, long long y) : x(x), y(y) {}
};
Point dp[20][10][10][10][10][2];
Point dfs(int len, int last1, int last2, int last3, int now, int sta, int limit) {
if (len == 0) {
if (sta != 0)
return Point(1, 0);
else
return Point(0, 0);
}
if (limit == 0 && dp[len][last1][last2][last3][now][sta].y != 0)
return dp[len][last1][last2][last3][now][sta];
Point ans(0, 0);
int Max = limit != 0 ? cnt[len] : 9;
int li;
for (int i = 0; i <= Max; ++i) {
Point t;
li = (limit != 0 && i == Max) ? 1 : 0;
if (last2 == 2 && last3 == 0 && now == 2 && i == 2)
t = dfs(len - 1, last2, last3, now, i, 1, li);
else
t = dfs(len - 1, last2, last3, now, i, sta, li);
ans.x += t.x;
ans.y += t.y + 1LL * i * ppow[len - 1] * t.x;
}
if (limit == 0)
dp[len][last1][last2][last3][now][sta] = ans;
return ans;
}
long long solve(long long x) {
memset(cnt, 0, sizeof(cnt));
int len = 0;
while (x > 0) {
cnt[++len] = x % 10;
x /= 10;
}
return dfs(len, 0, 0, 0, 0, 0, 1).y;
}
int main() {
for (int i = 0; i < 20; ++i) {
for (int j = 0; j < 10; ++j) {
for (int k = 0; k < 10; ++k) {
for (int l = 0; l < 10; ++l) {
for (int p = 0; p < 10; ++p) {
for (int q = 0; q < 2; ++q) {
dp[i][j][k][l][p][q] = Point(0, 0);
}
}
}
}
}
}
ppow[0] = 1;
for (int i = 1; i < 20; ++i) {
ppow[i] = ppow[i - 1] * 10;
}
int a, b;
cin >> a >> b;
cout << solve(b) - solve(a - 1) << endl;
return 0;
}
