1. 项目背景与核心挑战亲子游戏·最短路径拿最多糖果是华为ODOnline Judge机试中的一道经典算法题主要考察候选人对图论和动态规划的综合应用能力。题目模拟了一个亲子互动场景在一个N×M的矩阵网格中孩子从起点出发寻找糖果家长从另一端点出发拦截糖果双方每次只能向右或向下移动一格最终计算孩子在避开家长拦截的情况下能获得的最大糖果数。这道题之所以成为高频考题是因为它巧妙融合了三个关键算法思想矩阵中的双路径动态规划类似LeetCode 741摘樱桃问题博弈论中的对抗性路径选择带权图的最短路径变形Dijkstra或Bellman-Ford的变种注意实际解题时需要特别注意路径交叉时的糖果分配规则这是大多数考生失分的关键点。华为OD的测试用例往往会在这一点设置陷阱。2. 问题建模与算法选型2.1 输入输出规范典型的输入格式为3 4 # 网格行数n和列数m 1 2 3 4 # 每格糖果数 5 6 7 8 9 10 11 12输出要求返回孩子能获得的最大糖果总数。2.2 双DP解法思路主流解法采用双重动态规划正向DP记录孩子路径的最大糖果反向DP记录家长路径的最大糖果通过状态转移方程处理路径冲突# Python示例核心代码 def max_candies(grid): n, m len(grid), len(grid[0]) dp_child [[0]*m for _ in range(n)] dp_parent [[0]*m for _ in range(n)] # 孩子正向DP for i in range(n): for j in range(m): dp_child[i][j] grid[i][j] max( dp_child[i-1][j] if i0 else 0, dp_child[i][j-1] if j0 else 0 ) # 家长反向DP for i in range(n-1, -1, -1): for j in range(m-1, -1, -1): dp_parent[i][j] grid[i][j] max( dp_parent[i1][j] if in-1 else 0, dp_parent[i][j1] if jm-1 else 0 ) max_total 0 # 寻找不交叉路径的最大和 for i in range(n): for j in range(m): # 关键判断路径是否交叉 if not (i 0 and j m-1 and dp_child[i-1][j] dp_parent[i][j1]): max_total max(max_total, dp_child[i][j] dp_parent[i][j] - grid[i][j]) return max_total2.3 JS实现要点JavaScript版本需要注意使用TypedArray提升大型矩阵处理性能边界检查比Python更严格使用尾递归优化可能出现的栈溢出// JS核心逻辑 function maxCandies(grid) { const [n, m] [grid.length, grid[0].length]; const dpChild Array.from({length: n}, () new Uint32Array(m)); const dpParent Array.from({length: n}, () new Uint32Array(m)); // 初始化边界条件 dpChild[0][0] grid[0][0]; for (let i 1; i n; i) dpChild[i][0] dpChild[i-1][0] grid[i][0]; for (let j 1; j m; j) dpChild[0][j] dpChild[0][j-1] grid[0][j]; // ...其余DP逻辑与Python类似... }3. 关键难点与优化策略3.1 路径冲突处理当孩子和家长的路径在网格(i,j)点交叉时如果交叉发生在非边界点即i≠0且j≠m-1且孩子从上方的累计值等于家长从右方的累计值则需要排除该路径组合3.2 空间优化技巧可以将O(n²)空间复杂度优化到O(n)# 空间优化版 def max_candies_opt(grid): n, m len(grid), len(grid[0]) dp [0] * m # 第一行预处理 dp[0] grid[0][0] for j in range(1, m): dp[j] dp[j-1] grid[0][j] # 后续行处理 for i in range(1, n): dp[0] grid[i][0] for j in range(1, m): dp[j] max(dp[j-1], dp[j]) grid[i][j] return dp[-1]3.3 华为OD特判用例测试用例通常会包含以下特殊场景1x1网格直接返回该格值单行或单列网格变成简单累加负糖果值需要初始化DP数组为-∞大网格测试n,m 100时的性能考验4. 完整代码实现与测试4.1 Python最终实现def max_candies(grid): if not grid or not grid[0]: return 0 n, m len(grid), len(grid[0]) # 孩子DP dp_child [[0]*m for _ in range(n)] dp_child[0][0] grid[0][0] for i in range(1, n): dp_child[i][0] dp_child[i-1][0] grid[i][0] for j in range(1, m): dp_child[0][j] dp_child[0][j-1] grid[0][j] for i in range(1, n): for j in range(1, m): dp_child[i][j] max(dp_child[i-1][j], dp_child[i][j-1]) grid[i][j] # 家长DP dp_parent [[0]*m for _ in range(n)] dp_parent[-1][-1] grid[-1][-1] for i in range(n-2, -1, -1): dp_parent[i][-1] dp_parent[i1][-1] grid[i][-1] for j in range(m-2, -1, -1): dp_parent[-1][j] dp_parent[-1][j1] grid[-1][j] for i in range(n-2, -1, -1): for j in range(m-2, -1, -1): dp_parent[i][j] max(dp_parent[i1][j], dp_parent[i][j1]) grid[i][j] # 找最大和 max_sum 0 for i in range(n): for j in range(m): current dp_child[i][j] dp_parent[i][j] - grid[i][j] # 检查路径是否非法交叉 if i 0 and j m-1 and dp_child[i-1][j] dp_parent[i][j1]: continue if j 0 and i n-1 and dp_child[i][j-1] dp_parent[i1][j]: continue max_sum max(max_sum, current) return max_sum4.2 JavaScript最终实现function maxCandies(grid) { if (!grid || !grid.length || !grid[0].length) return 0; const n grid.length, m grid[0].length; const dpChild Array.from({length: n}, () new Array(m).fill(0)); const dpParent Array.from({length: n}, () new Array(m).fill(0)); // 初始化孩子DP dpChild[0][0] grid[0][0]; for (let i 1; i n; i) dpChild[i][0] dpChild[i-1][0] grid[i][0]; for (let j 1; j m; j) dpChild[0][j] dpChild[0][j-1] grid[0][j]; for (let i 1; i n; i) { for (let j 1; j m; j) { dpChild[i][j] Math.max(dpChild[i-1][j], dpChild[i][j-1]) grid[i][j]; } } // 初始化家长DP dpParent[n-1][m-1] grid[n-1][m-1]; for (let i n-2; i 0; i--) dpParent[i][m-1] dpParent[i1][m-1] grid[i][m-1]; for (let j m-2; j 0; j--) dpParent[n-1][j] dpParent[n-1][j1] grid[n-1][j]; for (let i n-2; i 0; i--) { for (let j m-2; j 0; j--) { dpParent[i][j] Math.max(dpParent[i1][j], dpParent[i][j1]) grid[i][j]; } } // 计算最大和 let maxSum 0; for (let i 0; i n; i) { for (let j 0; j m; j) { const current dpChild[i][j] dpParent[i][j] - grid[i][j]; // 检查路径冲突 if (i 0 j m-1 dpChild[i-1][j] dpParent[i][j1]) continue; if (j 0 i n-1 dpChild[i][j-1] dpParent[i1][j]) continue; maxSum Math.max(maxSum, current); } } return maxSum; }5. 华为OD机试实战技巧5.1 调试技巧先处理小规模测试用例如2x2网格打印中间DP矩阵验证状态转移特别注意网格索引的边界条件5.2 性能优化Python使用numpy数组代替二维列表JS使用Uint32Array类型化数组提前终止条件当剩余糖果不可能超过当前最大值时5.3 常见错误忘记处理路径交叉的情况家长DP的方向弄反应从右下往左上糖果重复计算合并时需要减去grid[i][j]我在实际测试中发现使用记忆化搜索的DFS方法虽然直观但在华为OD的大数据量测试用例下必然超时。双DP方案是唯一能通过所有测试的解法这也体现了华为对工程实践中算法效率的严格要求。