4969 字
25 分钟
动态规划算法详解：从CSP-S到IOI
动态规划算法详解：从CSP-S到IOI
动态规划（Dynamic Programming，DP）是算法竞赛中最重要的算法思想之一，从CSP-S到IOI各个级别的竞赛中都占据重要地位。本文将系统性地讲解动态规划的各种类型和技巧。
一、动态规划基本概念
1.1 什么是动态规划
动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它适用于具有重叠子问题和最优子结构性质的问题。
核心思想：
- 状态（State）：用一个或多个变量描述问题的某个局面
- 状态转移（Transition）：从已知状态推导出新状态的过程
- 最优子结构（Optimal Substructure）：问题的最优解包含子问题的最优解
1.2 动态规划的特征
- 重叠子问题：子问题会被多次计算，通过记忆化避免重复计算
- 最优子结构：问题的最优解可以由子问题的最优解构造
- 无后效性：一旦确定某个状态，这个状态之前的决策不会影响后续决策
1.3 动态规划的设计步骤
- 定义状态：确定用什么变量表示问题
- 找出状态转移方程：确定状态之间的关系
- 确定边界条件：初始状态的值
- 确定计算顺序：保证计算某状态时所依赖的状态已经计算
二、线性DP
线性DP是最基础的动态规划类型，状态按照线性顺序排列。
2.1 最长上升子序列（LIS）
问题描述：给定一个长度为n的序列，求最长的严格上升子序列的长度。
状态定义：dp[i] 表示以第i个元素结尾的最长上升子序列长度。
状态转移：
dp[i] = max(dp[j] + 1) 其中 j < i 且 a[j] < a[i]时间复杂度：O(n²)
#include <bits/stdc++.h>using namespace std;
int n;int a[5005], dp[5005];
int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; }
int ans = 0; for (int i = 1; i <= n; i++) { dp[i] = 1; // 至少包含自己 for (int j = 1; j < i; j++) { if (a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); }
cout << ans << endl; return 0;}优化版本：O(n log n)
使用贪心+二分的思想，维护一个数组d[]，其中d[len]表示长度为len的上升子序列的最小末尾元素。
#include <bits/stdc++.h>using namespace std;
int n;int a[100005], d[100005];
int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; }
int len = 0; for (int i = 1; i <= n; i++) { // 找到第一个 >= a[i] 的位置 int pos = lower_bound(d + 1, d + len + 1, a[i]) - d; d[pos] = a[i]; if (pos > len) len = pos; }
cout << len << endl; return 0;}2.2 最长公共子序列（LCS）
问题描述：给定两个序列A和B，求它们的最长公共子序列长度。
状态定义：dp[i][j] 表示A的前i个字符和B的前j个字符的最长公共子序列长度。
状态转移：
if A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])#include <bits/stdc++.h>using namespace std;
string a, b;int dp[1005][1005];
int main() { cin >> a >> b; int n = a.length(), m = b.length();
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i-1] == b[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } }
cout << dp[n][m] << endl; return 0;}2.3 最大子段和（Maximum Subarray）
问题描述：给定一个整数序列，求和最大的连续子序列。
状态定义：dp[i] 表示以第i个元素结尾的最大子段和。
状态转移：
dp[i] = max(dp[i-1] + a[i], a[i])#include <bits/stdc++.h>using namespace std;
int n;int a[100005];
int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; }
long long dp = a[1], ans = a[1]; for (int i = 2; i <= n; i++) { dp = max(dp + a[i], (long long)a[i]); ans = max(ans, dp); }
cout << ans << endl; return 0;}三、背包问题
背包问题是动态规划中非常经典的一类问题，CSP-S和省选中经常出现。
3.1 01背包
问题描述：有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，每个物品只能选一次，求最大价值。
状态定义：dp[i][j] 表示前i个物品，背包容量为j时的最大价值。
状态转移：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])#include <bits/stdc++.h>using namespace std;
int n, W;int w[1005], v[1005];int dp[1005][1005];
int main() { cin >> n >> W; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; }
for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { dp[i][j] = dp[i-1][j]; // 不选第i个 if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]); } } }
cout << dp[n][W] << endl; return 0;}空间优化：滚动数组
int dp[1005];
int main() { cin >> n >> W; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; }
for (int i = 1; i <= n; i++) { for (int j = W; j >= w[i]; j--) { // 倒序遍历 dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } }
cout << dp[W] << endl; return 0;}3.2 完全背包
问题描述：每个物品可以选无限次。
状态转移：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])注意：这里是dp[i][j-w[i]]而不是dp[i-1][j-w[i]]，因为可以重复选择。
int dp[1005];
int main() { cin >> n >> W; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; }
for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= W; j++) { // 正序遍历 dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } }
cout << dp[W] << endl; return 0;}3.3 多重背包
问题描述：第i个物品最多选c[i]次。
二进制优化：将数量为c的物品拆分成 1, 2, 4, …, 2^k, c-2^(k+1)+1 这样的若干组。
#include <bits/stdc++.h>using namespace std;
int n, W;int dp[100005];vector<pair<int, int>> items; // (weight, value)
int main() { cin >> n >> W;
for (int i = 1; i <= n; i++) { int w, v, c; cin >> w >> v >> c;
// 二进制拆分 for (int k = 1; k <= c; k *= 2) { items.push_back({w * k, v * k}); c -= k; } if (c > 0) { items.push_back({w * c, v * c}); } }
// 01背包 for (auto [weight, value] : items) { for (int j = W; j >= weight; j--) { dp[j] = max(dp[j], dp[j-weight] + value); } }
cout << dp[W] << endl; return 0;}3.4 分组背包
问题描述：物品分成若干组，每组最多选一个。
#include <bits/stdc++.h>using namespace std;
int n, W, k; // k组vector<pair<int, int>> group[105]; // group[i] 存储第i组的物品int dp[1005];
int main() { cin >> n >> W >> k;
for (int i = 1; i <= k; i++) { int cnt; cin >> cnt; for (int j = 0; j < cnt; j++) { int w, v; cin >> w >> v; group[i].push_back({w, v}); } }
for (int i = 1; i <= k; i++) { for (int j = W; j >= 0; j--) { // 尝试选择第i组的每个物品 for (auto [w, v] : group[i]) { if (j >= w) { dp[j] = max(dp[j], dp[j-w] + v); } } } }
cout << dp[W] << endl; return 0;}四、区间DP
区间DP的特点是在一段区间上进行状态转移，通常用于处理与区间相关的最优化问题。
4.1 石子合并
问题描述：n堆石子排成一排，每次合并相邻两堆，代价为两堆石子数量之和，求最小总代价。
状态定义：dp[i][j] 表示合并第i堆到第j堆的最小代价。
状态转移：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])其中 i <= k < j，sum[i][j] 是第i到j堆的石子总数#include <bits/stdc++.h>using namespace std;
int n;int a[305], sum[305];int dp[305][305];
int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[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; dp[i][j] = INT_MAX;
// 枚举分割点 for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]); } } }
cout << dp[1][n] << endl; return 0;}4.2 矩阵链乘法
问题描述：给定n个矩阵，求最优的乘法顺序，使得乘法次数最少。
矩阵A[p×q]和B[q×r]相乘需要p×q×r次运算。
状态定义：dp[i][j] 表示计算矩阵链A[i]...A[j]的最少运算次数。
#include <bits/stdc++.h>using namespace std;
int n;int p[105]; // p[i-1] × p[i] 是第i个矩阵的维度long long dp[105][105];
int main() { cin >> n; for (int i = 0; i <= n; i++) { cin >> p[i]; }
for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = LLONG_MAX;
for (int k = i; k < j; k++) { long long cost = dp[i][k] + dp[k+1][j] + (long long)p[i-1] * p[k] * p[j]; dp[i][j] = min(dp[i][j], cost); } } }
cout << dp[1][n] << endl; return 0;}五、树形DP
树形DP是在树结构上进行的动态规划，通常使用DFS进行状态转移。
5.1 树的直径
问题描述：求树中最长的路径长度。
方法一：两次BFS/DFS
- 从任意点出发找到最远点u
- 从u出发找到最远点v
- u到v的距离即为直径
方法二：树形DP
状态定义：dp[u] 表示以u为根的子树中，从u出发的最长路径。
#include <bits/stdc++.h>using namespace std;
const int N = 100005;int n;vector<pair<int, int>> g[N]; // {neighbor, weight}int dp[N]; // dp[u] = 从u向下的最长路径int ans = 0;
void dfs(int u, int fa) { dp[u] = 0; int max1 = 0, max2 = 0; // 最长和次长路径
for (auto [v, w] : g[u]) { if (v == fa) continue;
dfs(v, u); int len = dp[v] + w;
if (len > max1) { max2 = max1; max1 = len; } else if (len > max2) { max2 = len; } }
dp[u] = max1; ans = max(ans, max1 + max2); // 经过u的最长路径}
int main() { cin >> n; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); }
dfs(1, 0); cout << ans << endl; return 0;}5.2 树上背包
问题描述：树上每个节点有权值和体积，选择不超过W体积的节点，使得任意两个选中的节点不是祖先关系，求最大权值和。
状态定义：dp[u][j] 表示以u为根的子树中，选择体积不超过j的节点的最大权值。
#include <bits/stdc++.h>using namespace std;
const int N = 105;int n, W;int w[N], v[N]; // 体积和价值vector<int> g[N];int dp[N][N], size_subtree[N];
void dfs(int u, int fa) { dp[u][w[u]] = v[u]; size_subtree[u] = w[u];
for (int son : g[u]) { if (son == fa) continue;
dfs(son, u);
// 背包合并 for (int i = size_subtree[u]; i >= 0; i--) { for (int j = 0; j <= size_subtree[son]; j++) { if (i + j <= W) { dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[son][j]); } } }
size_subtree[u] += size_subtree[son]; size_subtree[u] = min(size_subtree[u], W); }}
int main() { cin >> n >> W; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; }
for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }
dfs(1, 0);
int ans = 0; for (int i = 0; i <= W; i++) { ans = max(ans, dp[1][i]); } cout << ans << endl; return 0;}六、状态压缩DP
当状态数量较少（通常n≤20）时，可以用二进制数表示状态，这就是状态压缩DP。
6.1 旅行商问题（TSP）
问题描述：给定n个城市和城市间的距离，求从城市0出发，经过所有城市恰好一次后回到起点的最短路径。
状态定义：dp[S][i] 表示已访问城市集合为S，当前在城市i的最短路径长度。
状态转移：
dp[S][i] = min(dp[S - {i}][j] + dist[j][i])其中 j ∈ S 且 j ≠ i#include <bits/stdc++.h>using namespace std;
int n;int dist[20][20];int dp[1<<20][20];const int INF = 1e9;
int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> dist[i][j]; } }
// 初始化 memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; // 从城市0出发
// 枚举所有状态 for (int S = 0; S < (1 << n); S++) { for (int i = 0; i < n; i++) { if (!(S & (1 << i))) continue; // i不在S中 if (dp[S][i] >= INF) continue;
// 尝试扩展到下一个城市 for (int j = 0; j < n; j++) { if (S & (1 << j)) continue; // j已访问
int newS = S | (1 << j); dp[newS][j] = min(dp[newS][j], dp[S][i] + dist[i][j]); } } }
// 所有城市都访问，回到起点 int fullS = (1 << n) - 1; int ans = INF; for (int i = 0; i < n; i++) { ans = min(ans, dp[fullS][i] + dist[i][0]); }
cout << ans << endl; return 0;}6.2 状态压缩技巧
常用位运算操作：
// 判断第i位是否为1bool check(int S, int i) { return (S >> i) & 1; }
// 将第i位设为1int set_bit(int S, int i) { return S | (1 << i); }
// 将第i位设为0int clear_bit(int S, int i) { return S & ~(1 << i); }
// 翻转第i位int flip_bit(int S, int i) { return S ^ (1 << i); }
// 枚举S的所有子集for (int sub = S; sub; sub = (sub - 1) & S) { // sub 是 S 的一个子集}
// 统计1的个数int popcount(int S) { return __builtin_popcount(S); }
// 最低位的1int lowbit(int S) { return S & -S; }七、数位DP
数位DP用于解决与数字的数位相关的计数问题。
7.1 数位DP模板
问题描述：统计区间[L, R]中满足某种条件的数的个数。
核心思想：按位构造数字，记录状态，避免重复计算。
状态定义：dp[pos][state][limit]
pos：当前处理到第几位state：题目相关的状态limit：是否受到上界限制
#include <bits/stdc++.h>using namespace std;
int digit[20]; // 存储数字的每一位long long dp[20][2]; // dp[pos][state]
// 计算从高位到低位第pos位，状态为state，是否有上界限制long long dfs(int pos, int state, bool limit) { // pos: 当前位置，state: 状态，limit: 是否贴着上界
if (pos == 0) { // 到达边界，返回方案数 return state符合条件 ? 1 : 0; }
if (!limit && dp[pos][state] != -1) { return dp[pos][state]; // 记忆化 }
int up = limit ? digit[pos] : 9; // 当前位的上界 long long res = 0;
for (int i = 0; i <= up; i++) { // 枚举当前位填i int newState = 根据i和state计算新状态; res += dfs(pos - 1, newState, limit && (i == up)); }
if (!limit) { dp[pos][state] = res; }
return res;}
long long solve(long long x) { if (x < 0) return 0;
int len = 0; while (x) { digit[++len] = x % 10; x /= 10; }
memset(dp, -1, sizeof(dp)); return dfs(len, 初始状态, true);}
int main() { long long L, R; cin >> L >> R;
cout << solve(R) - solve(L - 1) << endl; return 0;}7.2 例题：不含连续3个相同数字的数
问题：统计[L, R]中不包含连续3个相同数字的数的个数。
#include <bits/stdc++.h>using namespace std;
int digit[20];long long dp[20][10][3]; // dp[pos][last][cnt]// pos: 位置, last: 上一位数字, cnt: 连续相同数字个数
long long dfs(int pos, int last, int cnt, bool limit, bool lead) { if (pos == 0) return 1;
if (!limit && !lead && dp[pos][last][cnt] != -1) { return dp[pos][last][cnt]; }
int up = limit ? digit[pos] : 9; long long res = 0;
for (int i = 0; i <= up; i++) { if (lead && i == 0) { // 前导零 res += dfs(pos - 1, last, 0, limit && (i == up), true); } else { int newCnt = (i == last) ? cnt + 1 : 1; if (newCnt < 3) { // 不超过2个连续相同 res += dfs(pos - 1, i, newCnt, limit && (i == up), false); } } }
if (!limit && !lead) { dp[pos][last][cnt] = res; }
return res;}
long long solve(long long x) { if (x < 0) return 0;
int len = 0; while (x) { digit[++len] = x % 10; x /= 10; }
memset(dp, -1, sizeof(dp)); return dfs(len, 0, 0, true, true);}
int main() { long long L, R; cin >> L >> R; cout << solve(R) - solve(L - 1) << endl; return 0;}八、DP优化技巧
8.1 单调队列优化
适用场景：状态转移形如 dp[i] = min/max(dp[j] + cost) 其中 j ∈ [i-k, i-1]
例题：滑动窗口最大值
#include <bits/stdc++.h>using namespace std;
int n, k;int a[1000005];deque<int> q; // 存储下标
int main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; }
for (int i = 1; i <= n; i++) { // 移除队首过期元素 while (!q.empty() && q.front() < i - k + 1) { q.pop_front(); }
// 维护单调性（递减） while (!q.empty() && a[q.back()] <= a[i]) { q.pop_back(); }
q.push_back(i);
if (i >= k) { cout << a[q.front()] << " "; } }
return 0;}8.2 斜率优化（CHT）
适用场景：状态转移形如 dp[i] = min(dp[j] + (x[i] - x[j]) * y[j])
这可以转化为直线方程 y = kx + b 的形式，使用凸包维护。
核心思想：
- 将状态转移写成
dp[i] = min(k[i] * x[j] + y[j]) - 维护下凸壳（求最小值）或上凸壳（求最大值）
- 使用二分或指针查询最优决策点
struct Line { long long k, b; // y = kx + b
long long eval(long long x) { return k * x + b; }
// 判断是否需要删除中间的直线 bool bad(Line l1, Line l2) { // 检查l1是否比this和l2都差 return (__int128)(l2.b - b) * (k - l1.k) <= (__int128)(l1.b - b) * (k - l2.k); }};
deque<Line> hull;
void add_line(long long k, long long b) { Line newLine = {k, b};
// 维护下凸壳 while (hull.size() >= 2 && hull[hull.size()-1].bad(hull[hull.size()-2], newLine)) { hull.pop_back(); }
hull.push_back(newLine);}
long long query(long long x) { // 二分查找最优直线 int l = 0, r = hull.size() - 1; while (l < r) { int mid = (l + r) / 2; if (hull[mid].eval(x) > hull[mid+1].eval(x)) { l = mid + 1; } else { r = mid; } } return hull[l].eval(x);}8.3 四边形不等式优化
适用条件：满足四边形不等式的区间DP可以优化到O(n²)
四边形不等式：
w[i][j] + w[i+1][j+1] <= w[i][j+1] + w[i+1][j]决策单调性：
s[i][j-1] <= s[i][j] <= s[i+1][j]其中s[i][j]是dp[i][j]的最优决策点。
// 优化后的石子合并for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = INF;
// 使用决策单调性优化枚举范围 int L = (len == 2) ? i : s[i][j-1]; int R = (i == 1) ? j - 1 : s[i+1][j];
for (int k = L; k <= R; k++) { if (dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1] < dp[i][j]) { dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]; s[i][j] = k; } } }}九、IOI难度题目示例
9.1 IOI 2016 - Aliens（外星人）
问题简化版：给定n个二维平面上的点，选择k个正方形覆盖所有点，正方形边平行于坐标轴，最小化正方形面积之和。
解法：斜率优化DP + 二分
这是一个经典的”带权二分+DP”问题。
核心思路：
- 如果没有k的限制，可以用DP求解
- 使用WQS二分：给选择每个正方形一个代价λ，二分λ使得最优解恰好选k个
- 使用斜率优化将DP优化到O(n)
9.2 IOI 2014 - Holiday（假期）
问题：数轴上有n个城市，第i个城市有价值v[i]。起点在城市s，可以向左或向右走，每次移动花费1天，在城市可以获得价值。总共d天，求最大价值和。
解法：分治 + 贪心
- 分别考虑只向左、只向右、先左后右、先右后左四种情况
- 对于先左后右的情况，枚举左边走的距离，用主席树维护右边的最优方案
- 时间复杂度：O(n log² n)
十、总结
动态规划是算法竞赛中最重要的思想之一。从CSP-S到IOI，各个级别的DP题目层出不穷：
CSP-S级别：
- 线性DP（LIS、LCS）
- 基础背包问题
- 简单的区间DP
省选级别：
- 树形DP
- 状态压缩DP
- 数位DP
- 单调队列优化
NOI/IOI级别：
- 斜率优化、凸包优化
- 四边形不等式优化
- 插头DP、轮廓线DP
- 与其他算法结合（网络流、数据结构等）
学习建议：
- 打好基础：先掌握线性DP和背包问题
- 理解本质：重点理解状态定义和转移方程的推导
- 大量练习：DP需要大量题目练习来培养感觉
- 总结归纳：建立自己的DP题型分类和模板库
- 循序渐进：从简单题目开始，逐步提高难度
动态规划的核心是定义状态和找出转移方程。多思考、多练习，你也能成为DP高手！
推荐练习平台：
- 洛谷（Luogu）：大量分类DP题目
- Codeforces：高质量DP题
- AtCoder：DP题目质量很高
- USACO：从Bronze到Platinum的完整DP训练
祝大家在算法竞赛中取得好成绩！🎉
动态规划算法详解：从CSP-S到IOI
https://myblog-590.pages.dev/posts/algorithm-dp/