网站导航
> 技术文档 > 动态规划进阶：从理论到实战的 C++ 实现

动态规划进阶：从理论到实战的 C++ 实现

网友: 技术文档 2025-09-03 01:33:31

在算法竞赛和高级面试中，动态规划（Dynamic Programming, DP）是绕不开的核心考点。掌握基础 DP 只是起点，真正的挑战在于如何优化状态定义、加速状态转移，以及处理复杂场景下的 DP 问题。本文将深入探讨 DP 进阶技巧，并提供完整的 C++ 实现。

一、状态压缩 DP：用位运算优化集合表示

当 DP 状态需要表示 \"某个子集是否被选中\" 时，使用二进制位掩码（Bitmask）可以将状态压缩到整数范围内，大幅降低空间复杂度。

经典问题：旅行商问题（TSP）

旅行商问题是状态压缩 DP 的典型应用，目标是找到一条遍历所有城市且每个城市仅访问一次的最短路径。

状态定义：
dp[mask][u] 表示当前已访问城市集合为 mask（二进制表示），且当前位于城市 u 的最短路径长度。

状态转移：
对于每个未访问的城市 v，尝试从当前城市 u 转移到 v，更新状态：

cpp

运行

dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);

C++ 实现：

cpp

运行

#include #include #include #include using namespace std;int tsp(const vector<vector>& dist) { int n = dist.size(); int full_mask = (1 << n) - 1; vector<vector> dp(1 << n, vector(n, INT_MAX)); // 初始化：从城市0出发，已访问城市0 dp[1][0] = 0; // 遍历所有状态 for (int mask = 1; mask <= full_mask; ++mask) { for (int u = 0; u < n; ++u) { if (!(mask & (1 << u))) continue; // u不在mask中 for (int v = 0; v < n; ++v) { if (mask & (1 << v)) continue; // v已在mask中 int new_mask = mask | (1 < dp[mask][u] + dist[u][v]) {  dp[new_mask][v] = dp[mask][u] + dist[u][v]; } } } } // 计算回到起点的最短路径 int ans = INT_MAX; for (int u = 1; u < n; ++u) { if (dp[full_mask][u] != INT_MAX) { ans = min(ans, dp[full_mask][u] + dist[u][0]); } } return ans;}int main() { vector<vector> dist = { {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0} }; int min_cost = tsp(dist); cout << \"最短哈密尔顿回路长度: \" << min_cost << endl; return 0;}

二、斜率优化 DP：将 DP 转移转化为几何问题

当 DP 转移方程形如 dp[i] = min(f(j) + g(i) * h(j)) 时，可以使用斜率优化将时间复杂度从 O (n²) 降至 O (n)。

经典问题：任务安排问题

有 n 个任务需要安排，每个任务需要时间 t[i] 和费用系数 c[i]。每次启动机器需要时间 S，费用为启动时间乘以当前所有已安排任务的费用系数之和。求最小总费用。

状态定义：
dp[i] 表示安排前 i 个任务的最小总费用。

状态转移方程：

cpp

运行

dp[i] = min(dp[j] + sum_c[i] * (sum_t[i] + S - sum_t[j]))

其中 sum_t 和 sum_c 分别是时间和费用系数的前缀和。

斜率优化分析：
将转移方程变形为：
dp[j] = sum_c[i] * sum_t[j] + (dp[i] - sum_c[i] * (sum_t[i] + S))
这可以看作直线方程 y = kx + b，其中：

  • y = dp[j]
  • k = sum_c[i]（单调递增）
  • x = sum_t[j]
  • b = dp[i] - sum_c[i] * (sum_t[i] + S)

我们需要找到最小的截距 b，使得直线通过点 (sum_t[j], dp[j])。

C++ 实现：

cpp

运行

#include #include using namespace std;typedef long long LL;LL task_scheduling(const vector& t, const vector& c, int S) { int n = t.size(); vector sum_t(n + 1, 0), sum_c(n + 1, 0); vector dp(n + 1, 0); vector q(n + 1); // 单调队列 // 计算前缀和 for (int i = 1; i <= n; ++i) { sum_t[i] = sum_t[i - 1] + t[i - 1]; sum_c[i] = sum_c[i - 1] + c[i - 1]; } int head = 0, tail = 0; q[tail++] = 0; for (int i = 1; i <= n; ++i) { // 移除队首不合法的决策点 while (head + 1 < tail) { int j = q[head], k = q[head + 1]; LL yj = dp[j] + sum_c[n] * sum_t[j]; LL yk = dp[k] + sum_c[n] * sum_t[k]; if (yj - yk <= (sum_t[j] - sum_t[k]) * sum_c[i]) { head++; } else { break; } } int j = q[head]; dp[i] = dp[j] + sum_c[i] * (sum_t[i] + S - sum_t[j]); // 维护队列单调性 while (head + 1 = (yj_new - yk) * (sum_t[k] - sum_t[m])) { tail--; } else { break; } } q[tail++] = i; } return dp[n];}int main() { vector t = {1, 2, 3}; vector c = {3, 2, 1}; int S = 2; LL min_cost = task_scheduling(t, c, S); cout << \"最小总费用: \" << min_cost << endl; return 0;}

三、树形 DP：在树结构上的动态规划

树形 DP 是处理树状结构优化问题的有效方法，通常通过 DFS 自底向上或自顶向下传递状态。

经典问题：树的最大独立集

给定一棵树，求不相邻节点构成的最大权值和（独立集）。

状态定义：
dp[u][0]：不选节点 u 的情况下，以 u 为根的子树的最大权值和。
dp[u][1]：选节点 u 的情况下，以 u 为根的子树的最大权值和。

状态转移：

cpp

运行

dp[u][0] = sum(max(dp[v][0], dp[v][1])) // v是u的子节点dp[u][1] = val[u] + sum(dp[v][0]) // 选u则不能选子节点v

C++ 实现：

cpp

运行

#include #include using namespace std;const int MAXN = 10005;vector adj[MAXN]; // 邻接表存储树int val[MAXN]; // 节点权值int dp[MAXN][2]; // dp[u][0/1]: 不选/选节点u的最大权值和// 深度优先搜索处理树形DPvoid dfs(int u, int parent) { dp[u][0] = 0;  // 不选u，子节点可选可不选 dp[u][1] = val[u]; // 选u，子节点必须不选 for (int v : adj[u]) { if (v == parent) continue; // 避免重复访问父节点 dfs(v, u); // 不选u，子节点v可选可不选，取最大值 dp[u][0] += max(dp[v][0], dp[v][1]); // 选u，子节点v必须不选 dp[u][1] += dp[v][0]; }}int main() { int n = 5; // 节点数 // 初始化节点权值 val[1] = 1; val[2] = 2; val[3] = 3; val[4] = 4; val[5] = 5; // 构建树结构（示例：以1为根的树） adj[1].push_back(2); adj[2].push_back(1); adj[1].push_back(3); adj[3].push_back(1); adj[2].push_back(4); adj[4].push_back(2); adj[2].push_back(5); adj[5].push_back(2); // 从根节点1开始DFS dfs(1, -1); // 最终结果为选或不选根节点的最大值 int max_value = max(dp[1][0], dp[1][1]); cout << \"最大独立集权值和: \" << max_value << endl; return 0;}

四、区间 DP：处理区间合并问题

区间 DP 通常用于解决 “合并区间” 或 “分割区间” 的优化问题，状态设计一般为 dp[i][j] 表示处理区间 [i,j] 的最优解。

经典问题：石子合并

有 n 堆石子排成一排，每次可以将相邻的两堆合并成一堆，合并的代价为两堆石子的数量之和。求将所有石子合并成一堆的最小总代价。

状态定义：
dp[i][j] 表示合并区间 [i,j] 的最小总代价。

状态转移：

cpp

运行

dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum[i][j] // i ≤ k < j

其中 sum[i][j] 是区间 [i,j] 的石子总数。

C++ 实现：

cpp

运行

#include #include #include using namespace std;int stone_merge(const vector& stones) { int n = stones.size(); vector sum(n + 1, 0); vector<vector> dp(n + 1, vector(n + 1, 0)); // 计算前缀和 for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + stones[i - 1]; } // 枚举区间长度 for (int len = 2; len <= n; ++len) { for (int i = 1; i <= n - len + 1; ++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]); } } } return dp[1][n];}int main() { vector stones = {3, 2, 4, 1}; int min_cost = stone_merge(stones); cout << \"最小合并代价: \" << min_cost << endl; return 0;}

五、实战建议

  1. 状态设计原则：

    • 用最少的变量表示完整状态
    • 优先考虑低维状态，避免冗余信息
    • 利用对称性和隐含条件削减状态空间

  2. 优化方向：

    • 状态压缩：用位运算、哈希等技术降低空间复杂度
    • 转移优化：预处理、数据结构维护、斜率优化等
    • 预处理：前缀和、后缀和、单调栈 / 队列等技术

  3. 常见问题模式识别：

    • 集合问题 → 考虑状态压缩 DP
    • 区间合并 → 区间 DP
    • 树状结构 → 树形 DP
    • 决策单调性 → 斜率优化或四边形不等式优化

掌握这些进阶技巧后，你将能够解决更复杂的 DP 问题，如多约束背包问题、带权区间覆盖、树形依赖选择等高级问题。动态规划的核心在于状态设计和转移方程的推导，需要通过大量练习培养 “模式识别” 能力。

网络标签：

相关问题