1. 项目概述从一道题看华为OD机试的实战思维最近在帮几个准备冲刺华为OD机试的朋友做模拟训练发现“获取最多食物”这道题出现的频率相当高也确实是检验候选人编程基本功和问题转化能力的绝佳试金石。这道题本身并不涉及特别高深的算法但它巧妙地将一个现实场景——比如动物捕食链中的能量传递——抽象成了一个经典的图论问题核心就是在一个有向图中寻找最大权路径。很多朋友第一次看到题目描述可能会有点懵不知道从何下手或者写出来的代码在边界条件上总是出问题。今天我就结合自己当年备考和后来参与面试官培训的一些经验把这道题的里里外外彻底拆解一遍给出C、Java、Python三种语言的实现参考并重点分享那些官方题解里不会写的“踩坑实录”和优化技巧。无论你是刚开始刷题的新手还是已经有一定基础但在动态规划或深度优先搜索DFS上感觉不牢靠的同学这篇文章都会带你走一遍完整的思考过程。我们会从最朴素的暴力思路开始逐步优化到记忆化搜索和动态规划并讨论不同数据规模下的选型策略。你会发现吃透这一道题相当于复习了图论遍历、递归、动态规划等多个核心知识点性价比极高。2. 问题核心与场景抽象2.1 题目描述还原与理解首先我们得把题目描述还原出来。虽然原题描述可能因版本略有差异但核心模型是一致的。通常题目会这样描述有一个生态系统其中有N个生物节点编号从0到N-1。每个生物i拥有一定数量的食物权重记为food[i]。同时存在一些捕食关系有向边。如果存在一条从生物j指向生物i的边意味着生物i可以捕食物种j并获取j的全部食物。一个生物可以捕食多个其他生物但每个生物只能被一个捕食者捕获即每个节点的入度最多为1这很关键它保证了图的拓扑结构是多个链或树的集合而不是复杂的网。你的目标是找出一个生物作为起点沿着捕食链一直进行下去最终能获得的食物总量最大是多少。举个例子假设有4个生物食物量分别为[5, 10, 15, 20]。 捕食关系为0 - 1, 1 - 2, 3 - 2。 这意味着生物1可以捕食0获得5食物加上自己的10总共15。生物2可以捕食1从而间接获得0的食物也可以捕食3。如果捕食1可以获得15来自1 15自身 30如果捕食3可以获得20来自3 15自身 35。显然生物2选择捕食3更优。注意生物2不能同时捕食1和3题目隐含了每个生物只能进行一次捕食选择或者说捕食关系是确定的我们需要计算的是沿着既定关系链的累计和。经过抽象我们发现这本质上是一个在有向无环图DAG上求最大路径和的问题。由于每个节点入度≤1整个图是由若干条链或入度为0的单个节点组成的。我们的目标就是找出所有链中从某个节点到其所能到达的末端节点即没有捕食者的节点的路径上节点权重之和最大的那一条。2.2 关键约束与建模分析理解题目背后的约束是正确建模的第一步这里有几个容易忽略的要点入度限制题目通常保证每个生物最多被一个捕食者捕食。这意味着整个图是由若干条单向链或孤点组成的不存在一个节点有多个前驱从而形成“Y”型分支的情况。这个限制极大地简化了问题我们可以将每条链独立处理。如果没有这个限制问题将变为在一般DAG上求最长路径需要使用拓扑排序动态规划复杂度会稍高。食物量非负food[i]的值通常是非负整数。这一点很重要它保证了“子问题最优则全局最优”的性质我们的动态规划或DFS才能正确工作。如果存在负值就变成了带负权的最长路径问题需要不同的解法如Bellman-Ford判断正环但机试题中通常不会这么考。起点与终点路径的起点可以是任何一个生物。终点则是这条链上最后一个生物即没有捕食对象的生物。我们需要计算所有可能的链的累计和。输出要求最终输出是一个整数即能获得的最大食物总量。基于以上分析我们有两种主流的解决思路深度优先搜索DFS配合记忆化和动态规划DP。下面我们分别详解。3. 核心算法思路详解与对比3.1 思路一深度优先搜索DFS与记忆化这是最直观的递归思路。对于每个生物i它能获得的总食物等于它自己的食物food[i]加上它捕食的生物即它的后继节点能获得的最大总食物。定义状态设dp[i]表示以生物i为起点即捕食链从i开始所能获得的最大食物总量。状态转移如果生物i可以捕食生物j即存在边i - j那么dp[i] food[i] dp[j]。如果i没有可以捕食的对象即出度为0那么dp[i] food[i]。由于整个图是链式的一个节点的值依赖于它的后继节点而后继节点又依赖于它的后继最终会到达链尾。我们可以用DFS递归地计算每个节点的dp值。为什么需要记忆化考虑一条长链A-B-C-D。计算dp[A]需要dp[B]计算dp[B]需要dp[C]……如果我们在计算完dp[D]后没有把结果存下来那么当其他节点虽然在本例中由于入度限制没有但在递归思想中需要考虑也需要dp[D]时就会重复计算。记忆化搜索Memoization就是把已经计算过的dp[i]保存起来下次需要时直接返回避免重复递归将时间复杂度从指数级降为线性O(N)。算法步骤根据输入构建图。由于每个节点入度≤1我们可以用一个数组next[i]来存储节点i的后继节点编号。如果i没有后继则next[i] -1。初始化一个记忆化数组memo长度N初始值设为-1或一个不可能的值表示未计算。定义一个递归函数dfs(u)如果memo[u] ! -1直接返回memo[u]。如果next[u] -1说明u是链尾memo[u] food[u]。否则memo[u] food[u] dfs(next[u])。返回memo[u]。遍历所有节点i(0 到 N-1)计算dfs(i)并记录最大值。注意这里遍历所有节点调用dfs是必要的因为图由多条独立的链组成我们需要找到所有链的起点即入度为0的节点并计算其值。实际上由于记忆化的存在即使从链中某个节点开始调用dfs它也会递归到链尾并正确计算整条链从该点向后的和但最终比较最大值时链起点的值一定是该链上所有节点dp值中最大的。为了清晰和效率我们可以只对入度为0的节点链起点调用dfs。3.2 思路二动态规划自底向上递推既然图是若干条链我们也可以不用递归而是用迭代的方式从链尾向链头递推。这需要我们先找到所有的链尾出度为0的节点。算法步骤构建图同样使用next[i]数组。同时我们可以统计每个节点的入度inDegree[i]虽然题目说入度≤1但统计一下有助于找到链尾。初始化dp数组dp[i] food[i]。我们需要按照“从链尾到链头”的顺序计算dp。如何获得这个顺序由于图是链我们可以用类似拓扑排序的思路但更简单先找到所有链尾出度为0即next[i] -1的节点将它们放入一个队列。从队列中处理节点取出节点u它代表当前链的末端或一段的末端它的dp[u]已经确定初始就是food[u]。找到u的前驱节点v即存在边v - u。这需要我们在建图时也保存反向边或者遍历next数组效率低。更高效的做法是同时维护一个prev数组prev[u]表示u的前驱节点。如果存在前驱v则更新dp[v] max(dp[v], food[v] dp[u])。这里用max是因为理论上一个节点可能有多个前驱不根据约束入度≤1所以最多只有一个前驱这个max可以省略但保留能使代码更通用。然后将前驱节点v的入度减1虚拟的如果减到0意味着v的所有后继都已处理完则将v加入队列。处理完队列后dp数组中的最大值就是答案。两种思路对比DFS记忆化思路直观代码简洁尤其适合递归思维。在链式结构上由于递归深度可能等于链长需要注意编程语言默认的递归栈深度限制Python通常约1000。对于节点数N上万的长链可能会有栈溢出风险。DP递推迭代方法没有栈溢出风险性能稳定。需要额外维护前驱关系或进行查找代码稍显复杂但更体现“自底向上”的DP思想。在华为OD机试的环境下N通常不会大到导致递归栈溢出一般节点数在10^4以内递归深度也在这个量级两种方法都能AC。我个人更倾向于使用DFS记忆化因为写起来快不易错。4. 代码实现与逐行解析接下来我们分别用C、Java、Python实现DFS记忆化的解法。我会在代码中加入详细注释并指出每个版本需要特别注意的地方。4.1 C 实现#include iostream #include vector #include algorithm #include cstring // for memset using namespace std; int main() { int N; // 生物数量 cin N; vectorint food(N); for (int i 0; i N; i) { cin food[i]; } // next[i] 表示生物i捕食的生物编号-1表示没有捕食对象 vectorint next(N, -1); // 读取捕食关系假设输入M对关系每对是 (predator, prey) int M; cin M; for (int i 0; i M; i) { int u, v; cin u v; // u捕食v // 根据题目输入习惯可能需要调整u,v顺序。这里假设输入是捕食者u被捕食者v。 // 那么对于u来说它的后继是v。即 next[u] v。 // 但仔细看题通常描述是“i可以捕食j”那么i获得j的食物所以应该是从j指向i // 我们需要澄清方向这是最容易出错的地方。 // 定义如果i捕食j那么能量从j流向i。计算i的总食物时需要加上j的总食物。 // 因此j是i的前驱。我们在DFS时对于节点i需要找的是它的前驱j来计算吗不应该是找后继。 // 让我们统一一下我们定义 dp[i] 为从i开始作为捕食者能获得的最大食物。 // 那么如果i捕食j则 dp[i] food[i] dp[j]。这里j是i的后继i指向j。 // 所以建图时边应该是 i - j表示i捕食j。 // 输入格式通常是“被捕食者 捕食者”还是“捕食者 被捕食者”真题需要仔细看。 // 假设真题输入是“prey predator”即j i表示i捕食j。那么我们应该建立边 j - i。 // 为了安全我们根据样例调整。这里假设输入是 u v 表示 u 是捕食者v 是被捕食者。 // 那么能量从v流向u所以u的计算依赖于v。我们应该建边 u - v不对应该是v - u。 // 让我们换个思路我们最终要的是每个节点i的dp值dp[i] food[i] max(dp[j]) for j是i的后继。 // 如果i捕食j那么j是i的食物来源j应该在i之前被计算不对dp[i]依赖于dp[j]所以j是i的后继。 // 所以如果i捕食j则建立边 i - j。 // 这样dfs(i)时如果next[i]j则 dp[i] food[i] dfs(j)。 // 这个逻辑是自洽的。我们按照这个来。 next[u] v; // u捕食v建立边 u-v } // 记忆化数组初始化为-1 vectorint memo(N, -1); // DFS函数 functionint(int) dfs [](int u) - int { if (memo[u] ! -1) return memo[u]; // 如果u没有捕食对象则其总食物就是自身的食物 if (next[u] -1) { memo[u] food[u]; } else { // 否则总食物 自身食物 捕食对象的总食物 memo[u] food[u] dfs(next[u]); } return memo[u]; }; int maxFood 0; // 遍历所有节点计算dp值并更新最大值 // 注意由于有记忆化这里直接遍历所有节点即可复杂度O(N) for (int i 0; i N; i) { maxFood max(maxFood, dfs(i)); } cout maxFood endl; return 0; }C实现要点方向判断这是最易错点。务必根据样例确定边的方向。上述代码中假设输入(u, v)表示u捕食v那么对于捕食者u它的总食物需要加上被捕食者v的总食物。因此在DFS时u依赖于v所以边是u - v。dfs(u)内部会调用dfs(v)。递归函数对象使用了std::function来定义递归Lambda方便捕获外部变量。也可以使用普通函数加全局/静态变量。记忆化初始化memo初始化为-1因为食物量非负-1可以安全地表示未计算状态。遍历所有节点即使图是多条链从任意节点开始DFS由于记忆化每个节点只会被计算一次。最终取所有节点dp值的最大值。也可以优化为只从入度为0的节点开始DFS但需要额外计算入度在上述代码中直接全遍历更简单。4.2 Java 实现import java.util.*; public class Main { private static int[] food; private static int[] next; private static int[] memo; public static void main(String[] args) { Scanner scanner new Scanner(System.in); int N scanner.nextInt(); food new int[N]; for (int i 0; i N; i) { food[i] scanner.nextInt(); } next new int[N]; Arrays.fill(next, -1); // 初始化为-1表示没有后继 int M scanner.nextInt(); for (int i 0; i M; i) { int u scanner.nextInt(); int v scanner.nextInt(); // 假设输入 u v 表示 u捕食v建立边 u-v next[u] v; } memo new int[N]; Arrays.fill(memo, -1); // 记忆化数组 int maxFood 0; for (int i 0; i N; i) { maxFood Math.max(maxFood, dfs(i)); } System.out.println(maxFood); scanner.close(); } private static int dfs(int u) { if (memo[u] ! -1) { return memo[u]; } if (next[u] -1) { // 没有捕食对象 memo[u] food[u]; } else { // 有捕食对象总食物 自身食物 捕食对象的总食物 memo[u] food[u] dfs(next[u]); } return memo[u]; } }Java实现要点静态变量将food,next,memo设为静态变量方便在dfs静态方法中访问。也可以将它们作为参数传递。数组初始化使用Arrays.fill(next, -1)和Arrays.fill(memo, -1)进行初始化确保未连接的节点值为-1。递归深度Java的默认递归栈深度也可能限制在几千左右。对于极端的长链测试用例有栈溢出风险。在机试平台上通常用例会避免这种极端情况。如果担心可以考虑用显式栈实现迭代DFS或者用DP递推法。4.3 Python 实现import sys sys.setrecursionlimit(100000) # 设置递归深度防止递归层数过多导致溢出 def main(): data sys.stdin.read().strip().split() if not data: return it iter(data) N int(next(it)) food [int(next(it)) for _ in range(N)] # 初始化next数组-1表示没有后继 next_node [-1] * N M int(next(it)) for _ in range(M): u int(next(it)) v int(next(it)) # 假设输入 u v 表示 u捕食v建立边 u-v next_node[u] v memo [-1] * N def dfs(u: int) - int: if memo[u] ! -1: return memo[u] if next_node[u] -1: memo[u] food[u] else: memo[u] food[u] dfs(next_node[u]) return memo[u] max_food 0 for i in range(N): max_food max(max_food, dfs(i)) print(max_food) if __name__ __main__: main()Python实现要点递归深度Python的默认递归深度限制通常1000是硬伤。对于链长可能超过1000的测试用例必须使用sys.setrecursionlimit提高限制。设置一个足够大的数如10^5是常见做法。输入读取使用sys.stdin.read()一次性读取所有输入再分割比多次调用input()在大量数据时更快是机试中的常用技巧。列表推导与迭代器用列表推导式初始化food用iter迭代数据代码简洁高效。记忆化装饰器也可以使用functools.lru_cache装饰器实现记忆化但这里需要next_node和food作为外部变量用闭包或全局变量更方便手动管理memo列表更直观。5. 边界条件与常见“坑点”实录即使算法思路清晰代码写出来也可能因为一些边界情况或理解偏差而丢分。下面是我总结的几个高频“坑点”。5.1 坑点一图的方向与依赖关系混淆这是最大的一个坑。题目描述“生物i可以捕食物种j”时能量流向是从j到i。但在计算时我们定义dp[i]为以i为起点能获得的总食物。那么i依赖于它的食物来源j吗不dp[i]应该依赖于i能捕食的下一级生物k如果存在。因为i捕食k后能获得k的所有食物。所以边应该是从i指向k表示i捕食k。如何确认看样例通常样例会给出一个简单的链和最终结果。根据样例反推边的方向。例如假设食物是[5,10,15]关系是(0,1)如果答案是2501015?那么可能是0捕食11捕食2不对。最稳妥的方法是自己画一个小图手动模拟一下计算过程看哪种建图方式能得到样例输出。5.2 坑点二节点编号从0还是1开始题目通常会说编号从0到N-1但输入样例有时会用1-based编号。务必统一成0-based索引来处理数组否则会导致数组越界。在读取边(u, v)时如果题目是1-based需要执行u--; v--。5.3 坑点三食物量为零与记忆化初始值如果food[i]可能为0那么记忆化数组的初始值就不能用0因为0可能是一个有效的计算结果。使用-1food[i]非负时或NonePython是安全的。5.4 坑点四递归栈溢出Python/Java如前所述Python必须设置sys.setrecursionlimit。Java虽然栈深一些但对于N10^5的长链递归深度也可能达到10^5有溢出风险。在机试中如果N很大就要考虑用迭代DP拓扑排序来规避此问题。5.5 坑点五多条链与最大值更新我们的算法遍历了所有节点即使是从链中间的节点开始DFS由于记忆化它计算的是从该节点向链尾方向能获得的总和。但整条链的最大值一定出现在链的起点入度为0的节点吗是的因为食物量非负从起点开始累加一定不小于从中间点开始。所以最终答案就是所有节点dp值中的最大值。但有一种特殊情况如果存在孤立的节点没有边连接那么它自身的food[i]也可能就是最大值。我们的遍历所有节点的方法已经涵盖了这种情况。6. 性能优化与进阶思考6.1 空间与时间优化上述DFS记忆化的方法时间复杂度和空间复杂度都是O(N)对于机试来说完全足够。但我们可以做一些微优化只从链头开始DFS先计算每个节点的入度只对入度为0的节点调用dfs。这样可以减少递归调用的入口但需要额外的O(N)空间存储入度并且需要遍历边来计算入度。在N很大时常数优化可能有效。in_degree [0] * N for u in range(N): v next_node[u] if v ! -1: in_degree[v] 1 max_food 0 for i in range(N): if in_degree[i] 0: # 只从链头开始 max_food max(max_food, dfs(i)) # 注意还需要考虑孤立节点入度出度都为0它们也是链头长度为1的链 # 上面的循环已经包含了孤立节点in_degree[i]0迭代DP拓扑排序完全避免递归。如前面思路二所述从所有链尾出度为0开始用队列进行类似BFS的递推。这种方法最稳定适合任何语言和任何数据规模。6.2 如果取消入度限制如果题目改为每个生物可以被多个捕食者捕食即入度可以大于1图就变成了一个真正的DAG。此时一个节点的dp值不再只依赖于一个后继而是依赖于所有它能捕食的后继节点中的最大值或和取决于规则。状态转移变为dp[i] food[i] max(dp[j])其中j是所有i能捕食的生物。计算顺序需要用到拓扑排序先计算入度为0的节点食物链底端然后逐步向上游计算。算法如下建图记录每个节点的后继列表graph[i]和入度inDegree[i]。初始化dp[i] food[i]。将所有入度为0的节点加入队列。BFS/拓扑排序出队节点u。遍历u的所有前驱节点p注意这里u是被捕食者p是捕食者。我们需要更新捕食者p的dp值。所以我们需要反向建图reverseGraph或者遍历所有节点找到以u为后继的节点效率低。对于每个前驱p更新dp[p] max(dp[p], food[p] dp[u])。并将p的入度减1如果减到0则入队。最后dp数组中的最大值即为答案。这个版本更通用但代码也复杂一些。在华为OD真题中“获取最多食物”通常有入度≤1的限制所以用链式DFS就够了。6.3 机试实战技巧先理解再动手花2-3分钟仔细读题用给的样例画图手动算一遍确保完全理解输入输出格式、边的方向、计算规则。先写注释再写代码在代码关键部分如建图、DFS函数、状态转移先写上中文注释理清逻辑避免写到一半思路混乱。自测样例写完代码后用题目给的样例、自己构造的边界样例如N1没有边有环但题目应保证无环进行测试。复杂度估算在代码开头简单注释时间和空间复杂度展示你的思考。Python选手注意递归深度sys.setrecursionlimit(100000)几乎是必写语句。这道“获取最多食物”题本质上考察的是对问题的抽象能力将故事转化为图模型和对基础算法DFS、DP的熟练应用。它不像动态规划中的背包问题那样有固定的模板需要你根据具体的图结构灵活定义状态和转移方程。希望这篇详细的拆解能帮你彻底掌握它。在OD机试中遇到类似问题比如“能量传输”、“最大收益”等变体你都能举一反三快速套用这个模型。
