网站开发需要哪些职位,做企业网站电话销售话术,网络营销工具和方法,做数据ppt模板下载网站前言#xff1a; 在上一篇中#xff0c;我们讲解了动态规划基础及线性、区间 DP 典型案例。本篇将聚焦 背包问题、树形 DP、状态压缩 DP 以及更高级的 DP 技巧#xff0c;如插值 DP、数位 DP 和树链剖分DP。通过这些内容#xff0c;你将全面提升动态规划问题的建模与求解能…前言 在上一篇中我们讲解了动态规划基础及线性、区间 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[N1][V1];
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[V1];
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 ^ (1i)][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 的应用边界。 动态规划是算法竞赛和工程优化的利器多练习、多归纳才能驾驭其强大威力。
