1. 题目背景与核心需求解析这道华为OD机试真题亲子游戏·最短路径拿最多糖果是一个典型的图论与动态规划结合的应用场景。题目描述了一位家长带着孩子在游乐场中游玩游乐场被建模为一个二维矩阵每个格子中放置了不同数量的糖果。家长和孩子从起点出发需要找到两条从起点到终点的路径家长一条孩子一条且两条路径不能有重叠的格子。目标是让这两条路径获得的糖果总数最大化。1.1 问题建模与抽象我们可以将这个问题抽象为输入一个M×N的二维矩阵每个元素代表该位置的糖果数量约束条件两条路径家长和孩子不能经过相同的格子路径只能向右或向下移动目标最大化两条路径获得的糖果总和这个问题可以看作是双线程的最短路径问题的变种类似于LeetCode上的Cherry Pickup问题。但与标准的最短路径问题不同我们需要同时考虑两条路径的优化。1.2 关键挑战点路径冲突处理如何确保两条路径不会交叉或重叠状态空间管理如何高效地表示和计算两条路径的状态最优子结构如何分解问题并利用动态规划的特性2. 算法设计与思路分析2.1 动态规划状态定义对于这类双路径问题常规的动态规划状态定义需要同时跟踪两条路径的位置。我们定义dp[i1][j1][i2][j2]表示第一条路径到达(i1,j1)第二条路径到达(i2,j2)时能获得的最大糖果数。但这样的四维状态空间复杂度太高O(n^4)。观察到两条路径是同步移动的步数相同我们可以优化为三维状态dp[k][i1][i2]表示两条路径都走了k步第一条路径在第i1行第二条路径在第i2行时的最大糖果数。此时j1 k - i1, j2 k - i2。2.2 状态转移方程对于每个状态dp[k][i1][i2]它可以由四种前驱状态转移而来每条路径有两种移动方向组合起来有四种可能两条路径都从上向下移动dp[k-1][i1-1][i2-1]第一条路径从上向下第二条路径从左向右dp[k-1][i1-1][i2]第一条路径从左向右第二条路径从上向下dp[k-1][i1][i2-1]两条路径都从左向右移动dp[k-1][i1][i2]我们需要取这四种情况的最大值并加上当前格子的糖果数。如果两条路径走到同一格子只能计算一次糖果。2.3 边界条件处理初始状态dp[0][0][0] grid[0][0]起点越界检查确保i1,i2,j1,j2在矩阵范围内终点处理当到达(M-1,N-1)时停止3. Java实现详解3.1 基础数据结构public class Solution { public int maxCandies(int[][] grid) { int m grid.length; if (m 0) return 0; int n grid[0].length; // dp[k][i1][i2] 表示走了k步第一条路径在第i1行第二条路径在第i2行时的最大糖果 int[][][] dp new int[m n - 1][m][n]; dp[0][0][0] grid[0][0]; // 其余代码... } }3.2 核心算法实现for (int k 1; k m n - 1; k) { for (int i1 0; i1 m; i1) { for (int i2 0; i2 n; i2) { int j1 k - i1; int j2 k - i2; // 检查是否越界 if (j1 0 || j1 n || j2 0 || j2 n) continue; // 当前格子糖果 int curr (i1 i2 j1 j2) ? grid[i1][j1] : grid[i1][j1] grid[i2][j2]; // 四种可能的转移 int maxPrev 0; if (i1 0 i2 0) maxPrev Math.max(maxPrev, dp[k-1][i1-1][i2-1]); if (i1 0 j2 0) maxPrev Math.max(maxPrev, dp[k-1][i1-1][i2]); if (j1 0 i2 0) maxPrev Math.max(maxPrev, dp[k-1][i1][i2-1]); if (j1 0 j2 0) maxPrev Math.max(maxPrev, dp[k-1][i1][i2]); dp[k][i1][i2] maxPrev curr; } } }3.3 结果提取与优化// 最终结果是dp[mn-2][m-1][n-1] return dp[m n - 2][m - 1][n - 1];4. Go语言实现对比4.1 Go实现特点Go语言的实现与Java类似但有几点需要注意Go的数组是值类型多维数组处理略有不同Go的slice使用更灵活内存管理方式不同4.2 完整Go实现func maxCandies(grid [][]int) int { m : len(grid) if m { return } n : len(grid[0]) // 初始化DP表 dp : make([][][]int, mn-1) for k : range dp { dp[k] make([][]int, m) for i : range dp[k] { dp[k][i] make([]int, n) } } dp[0][0][0] grid[0][0] // 动态规划过程 for k : 1; k mn-1; k { for i1 : ; i1 m; i1 { for i2 : ; i2 n; i2 { j1 : k - i1 j2 : k - i2 if j1 0 || j1 n || j2 0 || j2 n { continue } curr : grid[i1][j1] if !(i1 i2 j1 j2) { curr grid[i2][j2] } maxPrev : if i1 i2 { maxPrev max(maxPrev, dp[k-1][i1-1][i2-1]) } if i1 j2 { maxPrev max(maxPrev, dp[k-1][i1-1][i2]) } if j1 i2 { maxPrev max(maxPrev, dp[k-1][i1][i2-1]) } if j1 j2 { maxPrev max(maxPrev, dp[k-1][i1][i2]) } dp[k][i1][i2] maxPrev curr } } } return dp[mn-2][m-1][n-1] } func max(a, b int) int { if a b { return a } return b }5. 算法优化与性能分析5.1 空间复杂度优化当前的三维DP表空间复杂度为O(K×M×N)其中KMN-1。我们可以观察到每个状态只依赖于前一步的状态因此可以将空间复杂度优化到O(M×N)public int maxCandiesOptimized(int[][] grid) { int m grid.length; if (m 0) return 0; int n grid[0].length; int[][] dp new int[m][n]; dp[0][0] grid[0][0]; // 需要额外的临时数组存储前一步的状态 // 实现略... }5.2 时间复杂度分析原始算法的时间复杂度为O((MN)×M×N)在最坏情况下是O(N^3)。对于一般机试题的约束条件如M,N≤50这个复杂度是可以接受的。5.3 边界情况处理需要特别注意以下边界情况1×1的网格只有一行或一列的网格所有格子糖果数相同的情况某些格子糖果数为负的情况如果题目允许6. 测试用例设计与验证6.1 典型测试用例Test public void testMaxCandies() { Solution solution new Solution(); // 常规情况 int[][] grid1 { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; assertEquals(29, solution.maxCandies(grid1)); // 单行单列 int[][] grid2 {{1, 2, 3}}; assertEquals(0, solution.maxCandies(grid2)); // 无法找到两条不重叠路径 // 负糖果数 int[][] grid3 { {1, -5, 3}, {4, 5, -6}, {7, -8, 9} }; assertEquals(15, solution.maxCandies(grid3)); }6.2 测试技巧先测试小规模网格2×23×3测试极端情况全0全负全正测试无法找到两条路径的情况测试路径必须交叉才能获得最大糖果的情况7. 华为OD机试备考建议7.1 常见题型分析华为OD机试通常包含数据结构题树、图、链表等动态规划问题字符串处理数学与逻辑题7.2 解题技巧仔细阅读题目明确输入输出格式和约束条件先设计再编码先写出伪代码或状态转移方程边界条件优先先处理特殊情况测试驱动开发边写代码边测试7.3 资源推荐LeetCode动态规划专题《算法导论》动态规划章节华为OD往年真题合集在线判题系统牛客网、力扣等8. 实际应用场景扩展这类双路径优化问题在实际中有广泛的应用物流调度两辆货车从仓库出发最大化运输量网络传输两条并行数据传输路径的最大吞吐量游戏AI两个角色协同收集资源的最优策略机器人路径规划多机器人协作的任务分配理解这类问题的解法可以帮助解决更复杂的资源分配和协同优化问题。在实际工程中可能还需要考虑更多约束条件如路径长度限制动态变化的网格更多并行路径部分可共享的路径掌握基础算法后可以逐步扩展到这些更复杂的场景。