动态规划

2023年的CCF考纲中，给动态规划划定的范围是简单的一维DP，简单背包问题，区间类型动态规划。

对动态规划了解较少的同学，可以先从下面的三类DP模板入手。思考DP问题，其核心在于状态定义和状态转移方程，开始的时候想不到怎么办，那就是多积累状态转移方程。解决了50个DP题目，就自然理解了状态和状态转移的概念。

最大子段和

问题：给出一个长度为n的序列a，选出其中连续且非空的一段使得这段和最大。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. //状态定义 dp[i]表示以第i个数为结尾的最大子段和
  5. //状态转移 dp[i] = max(dp[i-1]+a[i], a[i]);
  7. const int N = 2e5+10;
  9. int n, dp[N], a[N];
  11. int main() {
  12.     cin >> n;
  13.     for (int i = 1; i <= n; i++) {
  14.         scanf("%d", &a[i]);
  15.     }
  16.     int nmax = -2e9;
  17.     for (int i = 1; i <= n; i++) {
  18.         //     和i-1为结尾的最大子段合并 自己独立成段
  19.         dp[i] = max(dp[i-1] + a[i], a[i]);
  20.         nmax = max(nmax, dp[i]);
  21.     }
  22.     cout << nmax;
  23.     return 0;
  24. }

最长上升子序列

最长上升子序列，是指在一个数组中找到一个子序列，它的数值严格递增，并且使这个子序列的长度尽可能长。 最长递增子序列的元素在原序列中不一定是连续的。

例如 A = [10,9,2,5,3,7,101,18] 的最长递增子序列是 [2,3,7,101]，其长度是 4 。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. // 状态定义 dp[i]表示以第i个数做结尾时，最长上升子序列的长度
  5. // 转移方程 如果a[i] > a[j], dp[i] = max(dp[i], dp[j] + 1);
  7. int dp[1005]; 
  8. int a[1005];
  10. int main() {
  11.     int n;
  12.     cin >> n;
  13.     for (int i = 1; i <= n; i++) {
  14.         scanf("%d", &a[i]);
  15.     }
  17.     int nmax = 0;
  19.     for (int i = 1; i <= n; i++) {
  20.         dp[i] = 1;
  21.         for (int j = 1; j < i; j++) {
  22.             if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
  23.         }
  24.         nmax = max(nmax, dp[i]);
  25.     }
  26.     cout << nmax;
  27.     return 0;    
  28. }

0-1背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是v[i]，得到的价值是w[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, V, ans, v[1005], w[1005];
  6. int dp[1005]; 
  7. // 状态定义 dp[i][j]表示讨论第i个物品，背包容量为j时，能取到的最大价值
  8. // 状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
  9. // 常用滚动数组优化一维 dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
  11. int main() {
  12.     cin >> n >> V;
  13.     for (int i = 1; i <= n; i++) {
  14.         cin >> v[i] >> w[i];
  15.     }
  16.     for (int i = 1; i <= n; i++) {
  17.         for (int j = V; j >= v[i]; j--) {
  18.             dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
  19.         }
  20.     }
  21.     cout << dp[V];
  22.     return 0;
  23. }

完全背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是v[i]，得到的价值是w[i] 。每件物品能取无限次，求解将哪些物品装入背包里物品价值总和最大。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, V, ans, v[1005], w[1005];
  6. int dp[1005]; 
  7. // 状态定义 dp[i][j]表示讨论第i个物品，背包容量为j时，能取到的最大价值
  8. // 状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
  9. // 常用滚动数组优化一维 dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
  10. // 和 0-1背包不同是转移顺序变化
  12. int main() {
  13.     cin >> n >> V;
  14.     for (int i = 1; i <= n; i++) {
  15.         cin >> v[i] >> w[i];
  16.     }
  17.     for (int i = 1; i <= n; i++) {
  18.         for (int j = v[i]; j <= V; j++) {
  19.             dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
  20.         }
  21.     }
  22.     cout << dp[V];
  23.     return 0;
  24. }

区间DP

区间DP的经典例题是出现在1995提高组的石子合并，下面以这个题目为例：

在一个圆形操场的四周摆放 NNN 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 222 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 NNN 堆石子合并成 111 堆的最小得分和最大得分。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N = 505;
  7. //状态表示：f[i][j]表示将 i到 j这一段石子合并成一堆的方案的花费最小值
  8. //转移方程：
  9. // i < j 时 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]) 
  10. // i = j 时 dp[i][j] = 0 
  12. int a[N], s[N], dp[N][N];
  14. int main() {
  15.     int n;
  16.     cin >> n;
  17.     for (int i = 1; i <= n; i ++) {
  18.         cin >> a[i];
  19.         s[i] += s[i-1] + a[i];
  20.     }
  22.     memset(f, 0x3f, sizeof(f));
  23.     // 区间 DP 枚举：长度+左端点 
  24.     for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数
  25.         for (int i = 1; i + len - 1 <= n; i ++) {
  26.             int j = i + len - 1; // 自动得到右端点
  27.             if (len == 1) {
  28.                 dp[i][j] = 0;  // 边界初始化
  29.                 continue;
  30.             }
  32.             for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
  33.                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i-1]);
  34.             }
  35.         }
  36.     }
  37.     cout << dp[1][n] << endl;
  38.     return 0;
  39. }