企业官网建设流程全解析

网站建设公司专业网站开发需求,wordpress产品分类插件,程序开发的基本步骤是什么?,深圳属于广东省吗难度#xff1a;困难 标签#xff1a;动态规划、树形DP、背包问题、DFS 一、题目描述 给定一个公司的员工层级关系#xff08;树形结构#xff09;#xff0c;每位员工都有购买自己股票的机会#xff1a; present[i]#xff1a;第 i 位员工今天购买股票的价格future[i…难度困难标签动态规划、树形DP、背包问题、DFS一、题目描述给定一个公司的员工层级关系树形结构每位员工都有购买自己股票的机会present[i]第 i 位员工今天购买股票的价格future[i]第 i 位员工明天卖出股票的预期价格hierarchy员工的上下级关系budget总投资预算核心规则每只股票最多购买一次如果员工的直属上司购买了股票该员工可以半价购买floor(present[i] / 2)不能用未来收益增加预算目标在预算限制内最大化总利润。示例示例 1输入n 3, present [5,2,3], future [8,5,6], hierarchy [[1,2],[2,3]], budget 7 输出12 解释买员工1(花费5)→买员工2(半价1)→买员工3(半价1) 利润(8-5)(5-1)(6-1)12示例 2输入n 3, present [4,6,8], future [7,9,11], hierarchy [[1,2],[1,3]], budget 10 输出10 解释买员工1(花费4)买员工3(半价4) 利润(7-4)(11-4)10二、问题分析2.1 关键洞察树形结构员工层级关系构成树需要树形DP预算约束有限预算下的最优化问题需要背包DP折扣机制父节点购买影响子节点价格状态需包含父节点信息多子节点需要在子节点间分配预算使用分组背包2.2 问题建模这是一个树形DP 分组背包的组合问题树形DP在树上做决策每个节点买/不买分组背包多个子节点间分配有限预算三、算法设计3.1 状态定义定义dfs(u)返回一个结果结构体typeresultstruct{dp0[]int// dp0[b]: 父节点不购买时预算b的最大收益dp1[]int// dp1[b]: 父节点购买当前节点可享半价时预算b的最大收益sizeint// 子树最大可能开销用于剪枝}状态含义dp0[b]父节点没买当前子树在预算 b 下的最大收益dp1[b]父节点买了当前节点可半价预算 b 下的最大收益size子树所有节点原价之和用于背包剪枝关键优化一次 DFS 计算所有预算 [0, budget] 的结果避免重复计算。3.2 状态转移对于每个节点u分两步计算步骤1分组背包合并所有子节点// 初始化子节点收益数组subProfit0:make([]int,budget1)// 子节点无折扣subProfit1:make([]int,budget1)// 子节点有折扣当前节点买了for_,child:rangechildren[u]{childResult:dfs(child)// 分组背包倒序遍历预算fori:budget;i0;i--{// 关键剪枝只遍历到 min(childResult.size, i)forsub:0;submin(childResult.size,i);sub{subProfit0[i]max(subProfit0[i],subProfit0[i-sub]childResult.dp0[sub])subProfit1[i]max(subProfit1[i],subProfit1[i-sub]childResult.dp1[sub])}}}步骤2考虑当前节点的买/不买cost:present[u]// 原价dCost:present[u]/2// 半价fori:0;ibudget;i{// 父节点不购买的情况dp0dp0[i]subProfit0[i]// 不买当前节点ificost{dp0[i]max(dp0[i],subProfit1[i-cost]future[u]-cost)// 买当前节点(原价)}// 父节点购买的情况dp1当前节点可半价dp1[i]subProfit0[i]// 不买当前节点ifidCost{dp1[i]max(dp1[i],subProfit1[i-dCost]future[u]-dCost)// 买当前节点(半价)}}3.3 核心优化1. 批量计算所有预算原始做法为每个预算值单独调用 DFS → O(n × budget³)优化做法一次返回所有预算的结果数组 → O(n × budget²)2. size 剪枝forsub:0;submin(childResult.size,i);sub{// 子树最多花费 size超过的预算遍历无意义}3. 状态分离用dp0和dp1分别处理父节点买/不买的情况避免用 boolean 参数递归减少状态空间四、代码实现typeresultstruct{dp0[]int// 父节点不购买时各预算下的最大收益dp1[]int// 父节点购买时当前节点可享受半价各预算下的最大收益sizeint// 子树最大可能开销用于剪枝}funcmaxProfit(nint,present[]int,future[]int,hierarchy[][]int,budgetint)int{// 构建邻接表g:make([][]int,n)for_,edge:rangehierarchy{parent,child:edge[0]-1,edge[1]-1g[parent]append(g[parent],child)}vardfsfunc(uint)result dfsfunc(uint)result{cost:present[u]// 原价dCost:present[u]/2// 半价// dp0[b]: 父节点不购买预算b的最大收益// dp1[b]: 父节点购买可半价预算b的最大收益dp0:make([]int,budget1)dp1:make([]int,budget1)// 子节点收益分组背包// subProfit0[b]: 子节点无折扣预算b的最大收益// subProfit1[b]: 子节点有折扣当前节点买了预算b的最大收益subProfit0:make([]int,budget1)subProfit1:make([]int,budget1)uSize:cost// 当前子树最大开销至少是当前节点的原价// 分组背包合并所有子节点for_,v:rangeg[u]{childResult:dfs(v)uSizechildResult.size// 累加子树开销// 倒序遍历预算避免重复使用fori:budget;i0;i--{// 关键剪枝只遍历到 min(childResult.size, i)forsub:0;submin(childResult.size,i);sub{// 子节点无折扣subProfit0[i]max(subProfit0[i],subProfit0[i-sub]childResult.dp0[sub])// 子节点有折扣当前节点购买subProfit1[i]max(subProfit1[i],subProfit1[i-sub]childResult.dp1[sub])}}}// 计算当前节点的 dp0 和 dp1fori:0;ibudget;i{// 父节点不购买的情况dp0[i]subProfit0[i]// 不买当前节点ificost{// 买当前节点原价 子节点享受折扣dp0[i]max(dp0[i],subProfit1[i-cost]future[u]-cost)}// 父节点购买的情况当前节点可半价dp1[i]subProfit0[i]// 不买当前节点ifidCost{// 买当前节点半价 子节点享受折扣dp1[i]max(dp1[i],subProfit1[i-dCost]future[u]-dCost)}}returnresult{dp0,dp1,uSize}}returndfs(0).dp0[budget]}funcmax(a,bint)int{ifab{returna}returnb}funcmin(a,bint)int{ifab{returna}returnb}五、示例推导示例 1n 3, present [5,2,3], future [8,5,6], budget 7树结构0 → 1 → 2节点编号从0开始叶子节点 2 (present3, future6)cost 3, dCost 1 无子节点subProfit0 和 subProfit1 全为 0 dp0[b]: 父节点不购买时的最大收益 b 3: 0 (买不起) b 3: 6-3 3 (买节点2原价) dp1[b]: 父节点购买时的最大收益当前节点可半价 b 1: 0 (买不起) b 1: 6-1 5 (买节点2半价) 返回: {dp0[0,0,0,3,3,3,3,3], dp1[0,5,5,5,5,5,5,5], size3}节点 1 (present2, future5)cost 2, dCost 1 子节点 [2]: childResult {dp0[0,0,0,3,3,3,3,3], dp1[0,5,5,5,5,5,5,5], size3} 分组背包合并子节点 subProfit0[b] 子节点无折扣时的收益 [0,0,0,3,3,3,3,3] subProfit1[b] 子节点有折扣时的收益 [0,5,5,5,5,5,5,5] 计算 dp0[b]: 父节点不购买 不买节点1: dp0[b] subProfit0[b] 买节点1(原价2): dp0[b] max(subProfit0[b], subProfit1[b-2] 5-2) dp0[2] max(0, 53) 8 ✓ (买节点1子节点2半价收益5) dp0[3] max(3, 53) 8 ... 计算 dp1[b]: 父节点购买当前节点可半价 买节点1(半价1): dp1[b] max(subProfit0[b], subProfit1[b-1] 5-1) dp1[1] max(0, 04) 4 ❌ dp1[1] max(0, 54) 9 ✓ (买节点1半价子节点2也半价) 返回: {dp0[0,0,8,8,8,8,8,8], dp1[0,9,9,9,9,9,9,9], size5}根节点 0 (present5, future8)cost 5, dCost 2 子节点 [1]: childResult 的 dp0[0,0,8,8,8,8,8,8], dp1[0,9,9,9,9,9,9,9] 分组背包合并 subProfit0[b] [0,0,8,8,8,8,8,8] (子节点无折扣) subProfit1[b] [0,9,9,9,9,9,9,9] (子节点有折扣) 计算 dp0[7]: 父节点不购买 不买节点0: dp0[7] subProfit0[7] 8 买节点0(原价5): dp0[7] max(8, subProfit1[7-5] 8-5) max(8, 93) 12 ✓ 最终答案: 12最优策略买节点0(花费5) → 买节点1(半价1) → 买节点2(半价1)总花费5 1 1 7总收益(8-5) (5-1) (6-1) 12示例 2n 3, present [4,6,8], future [7,9,11], budget 10树结构0 → [1, 2]叶子节点节点 1: {dp0中b≥6时为3, dp1中b≥3时为6, size6}节点 2: {dp0中b≥8时为3, dp1中b≥4时为7, size8}根节点 0分组背包合并两个子节点[1,2] 先加入节点1的收益再加入节点2的收益 subProfit0[10]: 不给子节点折扣 max(买节点1原价6得3, 买节点2原价8得3) 3 subProfit1[10]: 给子节点折扣当前节点买了 考虑节点1半价3得6, 节点2半价4得7 买节点2半价4得7 (预算6剩余可再买节点1半价3) 76 13 ❌ 只买节点2半价4得7 ✓ 计算 dp0[10]: 不买节点0: 3 买节点0(原价4): subProfit1[10-4] 7-4 subProfit1[6] 3 subProfit1[6] 7 (只买节点2半价4) 7 3 10 ✓ 最终答案: 10最优策略买节点0(花费4) → 买节点2(半价4)总花费4 4 8总收益(7-4) (11-4) 10六、复杂度分析时间复杂度O(n × budget²)n 个节点每个节点调用一次 DFS每个节点的背包DP外层 O(budget)内层最多 O(size) ≈ O(budget)有 size 剪枝实际复杂度更优空间复杂度O(budget)每个节点需要 4 个 O(budget) 的数组dp0, dp1, subProfit0, subProfit1递归栈深度 O(n)总空间 O(budget n)七、性能优化详解7.1 朴素解法的问题朴素想法dfs(u, budget, parentBought) - int// 为每个预算值单独计算dfs:func(u,remainBudgetint,parentBoughtbool)int{// 1. 不买当前节点resultknapsack(children,remainBudget,false)// 2. 买当前节点resultmax(result,profitknapsack(children,remainBudget-cost,true))returnresult}问题每次调用只返回单个预算值的结果knapsack 内部需要遍历所有子节点的所有预算组合大量重复计算时间复杂度O(n × budget³)7.2 优化策略核心思路一次计算所有预算的结果// 一次返回所有预算[0..budget]的结果dfs:func(uint)result{dp0:make([]int,budget1)// 所有预算的结果dp1:make([]int,budget1)// 通过背包DP一次性计算所有预算// ...returnresult{dp0,dp1,size}}优势避免重复计算同一节点的不同预算背包DP自然地处理所有预算size 剪枝进一步减少搜索空间7.3 性能对比指标朴素解法优化解法提升时间复杂度O(n×budget³)O(n×budget²)budget 倍空间复杂度O(n×budget×2)O(budget)n×2 倍重复计算大量几乎无-剪枝效果无size 剪枝显著测试用例对比n12, budget93朴素解法约 12 × 93³ ≈ 9,600,000 次操作 →超时优化解法约 12 × 93² ≈ 104,000 次操作 →通过性能提升约 92 倍八、知识回顾8.1 0-1背包问题基本问题有 n 个物品和容量为 W 的背包每个物品重量 w[i]价值 v[i]每个物品最多选一次。状态转移dp[i][w] max( dp[i-1][w], // 不选第i个物品 dp[i-1][w-w[i]] v[i] // 选第i个物品 )空间优化一维数组dp:make([]int,W1)fori:0;in;i{// 必须倒序遍历避免重复使用forw:W;wweight[i];w--{dp[w]max(dp[w],dp[w-weight[i]]value[i])}}倒序原因保证每个物品只用一次分组背包本题使用物品分为若干组每组最多选一个物品。for_,group:rangegroups{// 遍历每组forw:W;w0;w--{// 倒序遍历预算for_,item:rangegroup{// 遍历组内物品ifwitem.weight{dp[w]max(dp[w],dp[w-item.weight]item.value)}}}}本题应用每个子节点是一组组内物品是给该子节点的不同预算分配dfs(child, spend, parentBought)计算分配 spend 预算的价值8.2 树形DP通用框架核心思想在树结构上进行动态规划通常从叶子向根或用DFS递归。通用模板funcdfs(uint)State{// 1. 初始化当前节点状态state:initState()// 2. 递归处理子节点for_,child:rangechildren[u]{childState:dfs(child)// 3. 合并子节点状态statemerge(state,childState)}// 4. 根据子节点状态更新当前节点stateupdate(state,u)returnstate}子节点合并策略问题类型合并方式示例独立子问题直接求和sum(dp[child])有约束条件背包DP本题的预算分配互斥选择取最大/最小只能选一个子节点经典树形DP问题1. 打家劫舍 III (House Robber III)// 状态: dp[u][0/1] 不选/选节点u的最大价值dp[u][0]sum(max(dp[child][0],dp[child][1]))dp[u][1]value[u]sum(dp[child][0])2. 树的直径// 状态: dp[u] 以u为端点的最长路径diametermax(diameter,dp[child1]dp[child2]2)dp[u]max(dp[child])13. 本题树形DP 背包// 状态: dfs(u) - {dp0[], dp1[], size}// 一次返回所有预算的最优解8.3 本题算法思维链条识别树形结构 ↓ 考虑树形DP ↓ 发现预算约束 → 结合背包问题 ↓ 父子节点相互影响 → 状态需包含父节点信息 ↓ 多个子节点 → 需要分组背包分配预算 ↓ 性能瓶颈 → 批量计算所有预算 size剪枝 ↓ 最终解法树形DP 分组背包 批量计算优化九、关键技巧总结1. 识别问题类型树形结构→ 树形DP预算限制→ 背包问题组合优化→ 分组背包2. 状态设计优化// ❌ 朴素设计dfs(u, budget, parentBought) - int// ✅ 优化设计dfs(u) - result{dp0[], dp1[], size}关键一次返回所有预算的结果空间换时间3. 剪枝技巧用size限制背包搜索空间子树最多花费size超过此预算的遍历无意义在大数据下效果显著4. 分组背包注意事项必须倒序遍历预算避免重复使用子节点每个子节点是一个组在组内选择最优分配方案十、扩展思考如果允许卖空需要增加状态维度表示持仓情况如果折扣策略更复杂可以将折扣率作为参数传递如果是多叉树且深度很大考虑记忆化或启发式剪枝十一、参考资料树形DP经典问题 - OI Wiki背包问题九讲LeetCode 3562 官方题解总结本题是树形DP与分组背包的经典结合关键优化在于批量计算所有预算的结果和size 剪枝。这种空间换时间的思路将时间复杂度从 O(n×budget³) 优化到 O(n×budget²)使得大规模测试用例能够通过。掌握这类优化技巧有助于解决更复杂的树上优化问题。