沈阳优化网站网红推广
前言：
在上一篇中，我们讲解了动态规划基础及线性、区间 DP 典型案例。本篇将聚焦 背包问题、树形 DP、状态压缩 DP 以及更高级的 DP 技巧，如插值 DP、数位 DP 和树链剖分+DP。通过这些内容，你将全面提升动态规划问题的建模与求解能力。
一、背包问题
背包问题是动态规划最经典的应用场景之一，包含若干变种：
1. 0/1 背包
1.1 问题定义
给定 N 件物品，每件物品体积 vol[i]、价值 val[i]，以及一个容量为 V 的背包。每件物品只能选择 0 次或 1 次，求最大总价值。
1.2 状态定义与转移
-
定义
dp[i][j]为前 i 件物品、背包容量为 j 时的最大价值。 -
转移：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-vol[i]] + val[i]) -
边界：
dp[0][*] = 0,dp[*][0] = 0。
1.3 自底向上实现（二维）
int[][] dp = new int[N+1][V+1];
for (int i = 1; i <= N; i++) {for (int j = 0; j <= V; j++) {dp[i][j] = dp[i-1][j];if (j >= vol[i])dp[i][j] = Math.max(dp[i][j], dp[i-1][j-vol[i]] + val[i]);}
}
return dp[N][V];
1.4 一维滚动数组优化
-
注意倒序遍历容量，防止重复使用同一物品：
int[] dp = new int[V+1];
for (int i = 1; i <= N; i++) {for (int j = V; j >= vol[i]; j--) {dp[j] = Math.max(dp[j], dp[j-vol[i]] + val[i]);}
}
return dp[V];
2. 完全背包
2.1 定义
每种物品可以无限次选取。
2.2 转移
-
正序遍历容量：
for (int i = 1; i <= N; i++)for (int j = vol[i]; j <= V; j++)dp[j] = Math.max(dp[j], dp[j-vol[i]] + val[i]);
3. 多重背包
3.1 定义
每种物品有 cnt[i] 件可选。
3.2 转换策略
-
直接枚举：O(NVcnt)
-
二进制拆分优化：将
cnt[i]分解为若干二进制块，转化为多个 0/1 物品，复杂度 O(NVlog cnt)
int k = 1;
while (k < cnt[i]) {addItem(vol[i]*k, val[i]*k);cnt[i] -= k;k <<= 1;
}
addItem(vol[i]*cnt[i], val[i]*cnt[i]);
4. 背包问题的变种
-
分组背包：物品分组，每组只能选 0/1 件。
-
混合背包：部分物品 0/1，部分完全，多重共存。
通用做法：对不同类型物品分别使用不同遍历顺序。
二、树形 DP 与状态压缩
1. 树形 DP
1.1 问题场景
-
路径最大和：树中两节点路径权重最大。
-
树的直径：树上最长路径。
-
最小覆盖集（Vertex Cover）：选顶点使每条边至少有一个端点被选中。
1.2 树形 DP 通用思路
-
以根为起点，对树进行 DFS，将子树结果向上传递。
-
状态
dp[u][0/1]表示节点 u 未选/已选的最优解。
void dfs(int u, int parent) {dp[u][0] = 0;dp[u][1] = value[u];for (int v : children[u]) if (v != parent) {dfs(v, u);dp[u][0] += dp[v][1]; // u 不选，v 必选dp[u][1] += Math.min(dp[v][0], dp[v][1]);}
}
2. 状态压缩 DP
适用于 n ≤ 20 的子集枚举场景，如旅行商、集合划分。
2.1 旅行商 (TSP)
-
dp[mask][i]表示经过子集mask，终点为 i 的最短路径。 -
转移：
for mask, i: dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])
时间 O(n^22^n)，空间 O(n2^n)。
2.2 集合划分 / 多人配送
同理使用 mask 表示已覆盖元素/客户。
三、高级 DP 话题
1. 插值 DP
-
场景：插花、矩形切割。动态枚举插入或切割点。
-
转移类似区间 DP。
2. 数位 DP
-
场景：统计满足条件的整数个数。
-
思路：按高位逐步枚举，对前缀状态进行 DP。
3. 树链剖分 + DP
-
思路：将树分解为链段，对路径或区间 DP 使用线段树/前缀和优化。
四、本篇小结
-
背包系列：0/1、完全、多重及其优化方法；分组、混合背包可灵活组合。
-
树形 DP：将树问题映射为子树状态转移，处理路径或覆盖类型问题。
-
状态压缩 DP：子集枚举是 NP-hard 问题的近似或小规模精确解法。
-
高级技巧：插值 DP、数位 DP 和树链剖分+DP 扩展了 DP 的应用边界。
动态规划是算法竞赛和工程优化的利器，多练习、多归纳，才能驾驭其强大威力。