本文详解递归求解二维迷宫从左上角到右下角的最小通行成本时的典型错误：未正确处理越界情况导致结果失真，并给出修复方案、完整可运行代码及性能优化建议。
本文详解递归求解二维迷宫从左上角到右下角的最小通行成本时的典型错误：未正确处理越界情况导致结果失真，并给出修复方案、完整可运行代码及性能优化建议。
在解决“仅允许向右或向下移动”的迷宫最小成本路径问题时，递归是一种直观的建模方式：到达 (row, col) 的最小成本 = 当前格子成本 maze[row][col] + min(从上方 (row-1, col) 到达的成本, 从左方 (row, col-1) 到达的成本)。但原始实现存在一个关键逻辑漏洞：
public static int findMinCost(int[][] maze, int row, int col) {
if (row == 0 && col == 0) {
return maze[row][col];
}
int cost = 0;
if (row >= 0 && col >= 0) {
cost += Math.min(findMinCost(maze, row-1, col),
findMinCost(maze, row, col-1))
+ maze[row][col];
}
return cost;
}核心问题在于越界返回值不合理：当 row < 0 或 col < 0 时（例如尝试从 (0,0) 向左或向上走），if (row >= 0 && col >= 0) 条件不满足，cost 保持为 0 并直接返回。这等价于允许“非法路径”以零成本通行，严重干扰最小值比较——例如，若真实路径成本为 10，而某次越界分支错误返回 0，算法会误选该非法路径。
✅ 正确做法是：将所有越界状态视为不可达，赋予极大代价（如 Integer.MAX_VALUE），确保其在 Math.min() 中被自然淘汰：
public static int findMinCost(int[][] maze, int row, int col) {
// 基础情况：起点
if (row == 0 && col == 0) {
return maze[0][0];
}
// 越界检查：不可达，返回极大值避免干扰min计算
if (row < 0 || col < 0) {
return Integer.MAX_VALUE;
}
// 递归转移：取上方或左方的最小成本，加上当前格子成本
return Math.min(
findMinCost(maze, row - 1, col),
findMinCost(maze, row, col - 1)
) + maze[row][col];
}⚠️ 注意事项：
- 调用入口必须为 findMinCost(maze, n-1, m-1)（即目标终点坐标），而非 (n, m)；
- 此纯递归解法时间复杂度为 O(2^(n+m))，存在大量重复子问题（如 (i,j) 被多次计算）；
- 强烈建议升级为记忆化递归（Memoization），用二维数组缓存已计算结果：
public static int findMinCostMemo(int[][] maze, int row, int col, int[][] memo) {
if (row == 0 && col == 0) return maze[0][0];
if (row < 0 || col < 0) return Integer.MAX_VALUE;
if (memo[row][col] != -1) return memo[row][col]; // 已计算，直接返回
memo[row][col] = Math.min(
findMinCostMemo(maze, row-1, col, memo),
findMinCostMemo(maze, row, col-1, memo)
) + maze[row][col];
return memo[row][col];
}
// 使用示例：int[][] memo = new int[n][m]; Arrays.stream(memo).forEach(a -> Arrays.fill(a, -1));总结：递归求解路径类问题，越界处理是正确性的基石——不可简单返回 0 或忽略，而应返回语义明确的“无效值”；在此基础上，通过记忆化可将时间复杂度优化至 O(n×m)，兼顾简洁性与实用性。
