动态规划._动态规划算法的基本思想

动态规划

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题拆解为多个子问题，并通过记忆化避免重复计算，从而提高效率的算法思想。

它特别适用于具有重叠子问题和最优子结构性质的问题，常见于：背包问题、最长子序列、路径计数、区间合并、树形结构等场景。

---

一、动态规划的核心思想

把大问题拆成小问题，先解决小问题，保存结果，避免重复计算。

比如我们要求斐波那契数列第 n​ 项：

• 普通递归会重复计算很多次。
• 动态规划只算一遍每个子问题，并保存结果，效率大幅提升。

---

二、动态规划的基本步骤（五步法）

1. 确定状态
   ——用什么变量表示子问题？
2. 确定状态转移方程
   ——当前状态由哪些子状态推导来？
3. 确定初始条件（边界）
   ——最小子问题的解怎么写？
4. 确定遍历顺序
   ——从小到大求解，保证子问题先于大问题。
5. 最终答案的输出位置
   ——通常是最后一个状态，也可能是多个状态中的最优解。

---

三、举个例子：斐波那契数列

1. 状态表示：

​f[i]​ 表示第 i​ 项的值。

2. 状态转移：

​f[i] = f[i - 1] + f[i - 2]​

3. 初始条件：

​f[0] = 0​, f[1] = 1​

4. 实现代码（自底向上）

int fib(int n) { vector<int> f(n + 1); f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n];}

---

四、常见动态规划模型

类型 典型问题 状态含义 转移思路 线性 DP 最长上升子序列 ​f[i] = 以i结尾的LIS长度​ 枚举前面比它小的 背包 DP 0-1 背包问题 ​f[i][j] = 前i件物品在容量j下的最大价值​ 放 or 不放 区间 DP 合并石子、矩阵链乘 ​f[i][j] = 区间(i,j)的最优解​ 枚举分割点 树形 DP 树上独立集 ​f[u][0/1] = u不选/选的最大值​ 父子递归合并 状态压缩 DP 旅行商问题（TSP） ​f[mask][i] = 到i的最短路径​ 枚举上一个状态 记忆化搜索 多用于递归 + 缓存 ​dfs(i,j)​记下每个值 减少重复递归

---

五、注意事项

• 状态定义不清 → DP推不出来

• 没搞清子问题之间的依赖关系 → 状态转移错

• 数组维度开小了 → 越界

• 可以压缩空间的时候没压缩 → 空间超限

• ---

  ‍

六. 具体学习

背包问题

​​

​​

5.1.1 01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

8

思路：

​​

#include#include#include#includeusing namespace std;const int N=1005;int v[N*N],w[N*N]; // v[i] 表示第 i 件物品的体积, w[i] 表示第 i 件物品的价值int f[N][N]; // f[i][j] 表示前 i 件物品在容量 j 下的最大价值int n,m;int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; // 读取 n 件物品的体积和价值 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f[i][j]=f[i-1][j]; // 不选当前物品 i，则价值等于前 i-1 件物品的最优解 if(j>=v[i]) // 只有当容量 j 能放下物品 i 时才考虑选它 f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); // 选与不选取较优解 } } cout<<f[n][m]<<endl; // 输出前 n 件物品在容量 m 下的最大价值 return 0;}

优化到一维

#include#includeusing namespace std;const int N = 1005;int v[N], w[N], f[N]; // f[j] 只存一行数据，减少空间int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 读取 n 件物品的体积和价值 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; // 输出容量 m 下的最大价值 return 0;}

5.1.2 完全背包问题

有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

10

思路：

完全背包是求前缀的最大值，第一次求前1项的max，第二次求前2项的max，…

​​

#includeusing namespace std;const int N = 1010;int f[N][N]; // f[i][j] 表示前 i 件物品在容量 j 下的最大价值int v[N],w[N];int main(){ int n,m; 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=1;j<=m;j++) { f[i][j]=f[i-1][j]; // 不选当前物品 i if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); // 选当前物品 i，可重复选 } } cout<<f[n][m]<<endl; // 输出最大价值 return 0;}

优化到一维

#includeusing namespace std;const int N = 1010;int f[N], v[N], w[N];int main(){ int n, m; 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;}

5.1.3 多重背包问题I

有 N种物品和一个容量是 V 的背包。

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100

0<vi,wi,si≤100

输入样例

4 5

1 2 3

2 4 1

3 4 3

4 5 2

输出样例：

10

完全背包模型的基础上加了一个限制。

#include#include#include#includeusing namespace std;const int N=1010;int v[N],w[N],s[N]; // v[i]: 物品体积, w[i]: 物品价值, s[i]: 物品数量限制int f[N][N]; // f[i][j] 表示前 i 件物品在容量 j 下的最大价值int n,m;int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i]; // 读取每件物品的体积、价值和数量限制 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f[i][j]=f[i-1][j]; // 不选当前物品 i for(int k=1;k<=s[i];k++) // 枚举选取 k 件物品 i if(j>=k*v[i])  f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); // 选 k 件的最优解 } cout<<f[n][m]<<endl; // 输出最大价值 return 0;}

按照01背包进行优化为一维：

#include#includeusing namespace std;const int N = 1100;int n,m,v,w,s;int f[N];int main(){ scanf(\"%d%d\", &n,&m); for(int i=1;i<=n;i++) { cin>>v>>w>>s; for(int j=m;j>=0;j--) // 逆序遍历容量，保证物品不会被重复计算 for(int k=0;k<=s&&k*v<=j;k++) // 枚举当前物品的选取数量 k f[j]=max(f[j],f[j-k*v]+k*w); // 取选与不选的最优解 } cout<<f[m]<<endl; // 输出最大价值 return 0;}

5.1.4多重背包问题 II

有 N种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000

0<V≤2000

0<vi,wi,si≤2000

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 5

1 2 3

2 4 1

3 4 3

4 5 2

输出样例：

10

我们可以用二进制对其进行优化。

#includeusing namespace std;const int N = 12010, M = 2010;int n, m;int v[N], w[N]; // 存储物品的体积和价值（经过二进制拆分）int f[M]; // 01 背包的动态规划数组int main(){ cin >> n >> m; int cnt = 0; // 拆分后的物品数量 for(int i = 1; i <= n; i++) { int a, b, s; cin >> a >> b >> s; int k = 1; // 进行二进制拆分的当前数量 while(k <= s) { cnt++; // 增加新物品 v[cnt] = a * k; // 拆分出的物品体积 w[cnt] = b * k; // 拆分出的物品价值 s -= k; // 剩余数量减少 k *= 2; // 采用二进制倍增法 } // 处理剩余的部分 if(s > 0) { cnt++; v[cnt] = a * s; w[cnt] = b * s; } } n = cnt; // 物品数量变为拆分后的总数 // 01 背包一维优化 for(int i = 1; i <= n; i++) for(int j = m; j >= v[i]; j--) // 逆序遍历，避免状态污染 f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; // 输出最大价值 return 0;}

分组背包问题

有 N组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；

每组数据接下来有Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i个物品组的第 j个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100

0<Si<100

0<vij,wij≤100

输入样例

3 5

2

1 2

2 4

1

3 4

1

4 5

输出样例：

8

​​

#include#include#include#includeusing namespace std;const int N = 110;int w[N][N],v[N][N];int f[N][N];int s[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { cin>>s[i]; for(int k=1;k<=s[i];k++) cin>>v[i][k]>>w[i][k]; } for(int i=1;i<=n;i++) for(int j=1;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]<<endl; return 0;}

5.1.6二维背包的费用问题

有 N件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。

输出最大价值。

输入格式

第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N行，每行三个整数vi,mi,wi，用空格隔开，分别表示第 i件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000

0<V,M≤100

0<vi,mi≤100

0<wi≤1000

输入样例

4 5 6

1 2 3

2 4 4

3 4 5

4 5 6

输出样例：

8

思路：01背包的变形，多加了一个限制条件。

#include#include#includeusing namespace std;const int M = 1100;int N,V,W,x,y,z;int f[M][M];int main(){ cin>>N>>V>>W; for(int i=1;i<=N;i++) { cin>>x>>y>>z; for(int j=V;j>=x;j--) for(int k=W;k>=y;k--) f[j][k]=max(f[j][k],f[j-x][k-y]+z); } cout<<f[V][W]<<endl; return 0;}

线性DP

5.2.1数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输入格式

第一行包含整数 n，表示数字三角形的层数。

接下来 n行，每行包含若干整数，其中第 i 行表示数字三角形第 i层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500,

−10000≤三角形中的整数≤10000

输入样例：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出样例：

30

思路：

数字三角形的模型

​​

#include #include using namespace std;const int N = 510, INF = 1e9;int n;int a[N][N];int f[N][N];int main(){ scanf(\"%d\", &n); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) scanf(\"%d\", &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], f[i - 1][j])+a[i][j]; int res = -INF; for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); printf(\"%d\\n\", res); return 0;}

5.2.2最长上升子序列

给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000，

−1e9≤数列中的数≤1e9

输入样例：

7

3 1 2 1 8 5 6

输出样例：

4

思路：

​​

#include#include#include#includeusing namespace std;const int N = 1100;int a[N];int f[N];int n,ans;int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { f[i]=1; for(int j=1;j<i;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1); ans=max(ans,f[i]); } cout<<ans; return 0;}

5.2.3 最长上升子序列 II

给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤100000，

−1e9≤数列中的数≤1e9

输入样例：

7

3 1 2 1 8 5 6

输出样例：

4

​​

#include #include using namespace std;const int N = 100010;int n;int a[N];int q[N];//存储不同长度下，结尾的最小值int main(){ scanf(\"%d\", &n); for (int i = 0; i < n; i ++ ) scanf(\"%d\", &a[i]); int len = 0; 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];//r是小于a[i]的最大的数 } printf(\"%d\\n\", len); return 0;}

5.2.4最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

4 5

acbd

abedc

输出样例：

3

​​

#include#include#include#includeusing namespace std;const int N=1100;char A[N],B[N];int n,m;int f[N][N];int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>A[i]; for(int i=1;i<=m;i++) cin>>B[i]; 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;}

5.2.5最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

删除–将字符串 A 中的某个字符删除。

插入–在字符串 A 的某个位置插入某个字符。

替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

输入格式

第一行包含整数 n，表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m，表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

1≤n,m≤1000

输入样例：

10

AGTCTGACGC

11

AGTAAGTAGGC

输出样例：

4

​​

#include #include using namespace std;const int N = 1010;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); /*先初始化边界，当a的前0个字母与b匹配时只能添加和b对应位置上相同的字母,次数为a的长度*/ for (int i = 0; i <= m; i ++ ) f[0][i] = i; /*同理，当a与b的前0个字母匹配时，只能删除a中所有的字母，次数为a的长度*/ 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); } printf(\"%d\\n\", f[n][m]); return 0;}

5.2.6编辑距离

给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含一个字符串，表示给定的字符串。

再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过10。

输出格式

输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

1≤n,m≤1000,

输入样例：

3 2

abc

acd

bcd

ab 1

acbd 2

输出样例：

1

和上一题思路相同

#include #include #include using namespace std;const int N = 15, M = 1010;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(){ scanf(\"%d%d\", &n, &m); for (int i = 0; i < n; i ++ ) scanf(\"%s\", str[i] + 1); while (m -- ) { char s[N]; int limit; scanf(\"%s%d\", s + 1, &limit); int res = 0; for (int i = 0; i < n; i ++ ) if (edit_distance(str[i], s) <= limit) res ++ ; printf(\"%d\\n\", res); } return 0;}

区间DP

5.3.1石子合并

设有 N 堆石子排成一排，其编号为 1,2,3,…,N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 N 表示石子的堆数 N。

第二行 N 个数，表示每堆石子的质量(均不超过1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤N≤300

输入样例：

4

1 3 5 2

输出样例：

22

​​

#include#include#include#includeusing namespace std;const int N = 310;int a[N],s[N];int f[N][N];int n;int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int j=i+len-1; f[i][j]=1e8; for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); } } cout<<f[1][n]<<endl; return 0;}

计数类DP

5.4.1整数划分

​​

​​

思路：完全背包求方案数的模型。

完全背包解法

状态表示：

f[i][j]表示只从1~i中选，且总和等于j的方案数

状态转移方程:

f[i][j] = f[i - 1][j] + f[i][j - i];

二维

#include using namespace std;const int N = 1e3 + 7, mod = 1e9 + 7;int f[N][N];int main() { int n; cin >> n; for (int i = 0; i <= n; i ++) { f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案 } for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1 if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod; } } cout << f[n][n] << endl;}

一维优化

#include #include using namespace std;const int N = 1010, mod = 1e9 + 7;int n;int 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] + f[j - i]) % mod; cout << f[n] << endl; return 0;}

数位统计DP

5.5.1计数问题

​​

​​

​​

​​

#include #include #include using namespace std;const int N = 10;/*001~abc-1, 999abc 1. num[i]  x, 0~999*/int get(vector<int> num, int l, int r){ int res = 0; for (int i = l; i >= r; i -- ) res = res * 10 + num[i]; return res;}int power10(int x){ int res = 1; while (x -- ) res *= 10; return res;}int count(int n, int x){ if (!n) return 0; vector<int> num; while (n) { num.push_back(n % 10); n /= 10; } n = num.size(); int res = 0; for (int i = n - 1 - !x; i >= 0; i -- ) { if (i < n - 1) { res += get(num, n - 1, i + 1) * power10(i); if (!x) res -= power10(i); } if (num[i] == x) res += get(num, i - 1, 0) + 1; else if (num[i] > x) res += power10(i); } return res;}int main(){ int a, b; while (cin >> a >> b , a) { if (a > b) swap(a, b); for (int i = 0; i <= 9; i ++ ) cout << count(b, i) - count(a - 1, i) << \' \'; cout << endl; } return 0;}

树形DP

5.7.1 没有上司的舞会

​​

#include#define int long longusing namespace std;const int N=6e3+10;int n,w[N];vector<int> g[N];int f[N][3];int fa[N];void dfs(int u) {f[u][1]=w[u];for(auto x: g[u]) {dfs(x);f[u][0]+=max(f[x][0],f[x][1]);f[u][1]+=f[x][0];}}signed main() {cin>>n;for(int i=1;i<=n;i++) cin>>w[i];for(int i=1;i<n;i++) {int a,b;cin>>a>>b;g[b].push_back(a);fa[a]++;}int root=0;for(int i=1;i<=n;i++)if(!fa[i]) {root=i;break;} dfs(root);cout<<max(f[root][0],f[root][1]);return 0;}

状态压缩DP

状态压缩动态规划（DP）是一种将状态空间压缩的技术，主要通过位掩码（bitmask）来表示状态，以节省空间并提高计算效率。它通常用于处理有限状态的动态规划问题，比如求解旅行商问题（TSP）或求解子集问题等。

状态压缩动态规划常见的应用场景：

1. 子集问题：对于一个集合，求解所有子集的最优解。
2. 旅行商问题（TSP） ：求解在给定城市集合中，访问所有城市并返回起点的最短路径。
3. 排列组合问题：处理大量的排列或组合问题，状态压缩能够帮助减少内存使用。

旅行商问题（TSP）示例

假设有 n​ 个城市，要求找到一条路径访问所有城市，并返回起点，路径总长度最短。每个城市之间有已知的距离。

旅行商问题的状态压缩动态规划实现：

#includeusing namespace std;const int N = 16; // 假设最多有15个城市const int INF = 1e9;int dist[N][N], dp[1 << N][N]; // dp[i][j] 表示访问了状态 i 的所有城市，最后在城市 jint n;int TSP() { // 初始化 dp 数组，设置为 INF memset(dp, 0x3f, sizeof(dp)); // 将 dp 数组初始化为 INF dp[1][0] = 0; // 从城市 0 开始，只有第 0 城市被访问 // 遍历所有状态 for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if (mask & (1 << u)) { // 如果 u 城市已经在状态 mask 中 for (int v = 0; v < n; v++) {  if (!(mask & (1 << v))) { // 如果 v 城市不在状态 mask 中 dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);  } } } } } int ans = INF; // 找到最短路径，回到起点 for (int i = 1; i < n; i++) { ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]); } return ans;}int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> dist[i][j]; } } cout << TSP() << endl; return 0;}

代码解释：

1. ​​dist[i][j]​ ​：表示城市 i​ 到城市 j​ 的距离。

2. ​​dp[mask][i]​ ​：表示当前已经访问过的城市集合为 mask​，且当前在城市 i​ 时的最短路径。

   • ​mask​ 是一个位掩码，用于表示哪些城市已经被访问过。
   • ​i​ 是当前的城市，表示在状态 mask​ 中，最后一个访问的城市是 i​。

3. ​​TSP()​ ​：动态规划函数。我们初始化 dp[1][0] = 0​，表示从城市 0​ 出发，当前城市为 0​，没有任何城市被访问。

4. 状态转移：遍历每个状态 mask​ 和每个城市 u​，如果城市 u​ 在状态 mask​ 中，就尝试访问一个未访问过的城市 v​，更新状态 mask | (1 << v)​，即表示添加城市 v​ 到已访问城市集合中，并且更新路径的长度。

5. 最终结果：遍历所有城市 i​，得到从城市 i​ 返回起点的最短路径。

时间复杂度：

• 状态空间大小为 O(2^n * n)​，即每个状态有 2^n​ 种可能，每种状态有 n​ 个城市可选择。
• 因此，时间复杂度为 O(n^2 * 2^n)​，适用于城市数量较少（例如 n <= 15​）的场景。

状态压缩常见问题：

1. 最大状态数：对于每一个状态，我们使用一个位掩码来表示。如果状态数过多（例如 n​ 很大），可能会超出内存限制。
2. 位操作：位操作是核心，尤其是在处理集合时。位运算（如 mask | (1 << v)​）允许我们高效地处理状态空间。