递归实现迷宫遍历最小路径成本：代码错误排查求助

核心错误分析 #

原代码存在三个关键问题，导致输出结果不正确：

• 无效路径未过滤：当递归传入row-1 < 0或col-1 < 0时，这类路径本应被判定为无效，但原代码未做处理，反而继续参与成本计算，引发错误。
• 边界场景缺失处理：仅处理了起点(0,0)的情况，未考虑第一行（仅能从左侧移动）、第一列（仅能从上方移动）的特殊情况，导致错误调用无效递归分支。
• 错误初始值设定：cost初始化为0，无效路径返回的0会被当作有效成本参与最小值计算，导致最终结果偏小。

修复后的递归代码 #

public static int findMinCost(int[][] maze, int row, int col) {
    // 越界路径直接返回极大值，标记为不可选
    if (row < 0 || col < 0) {
        return Integer.MAX_VALUE;
    }
    // 到达起点，返回起点的成本
    if (row == 0 && col == 0) {
        return maze[row][col];
    }
    // 取上方或左侧路径的最小成本，加上当前单元格的成本
    int minPrevCost = Math.min(findMinCost(maze, row - 1, col), findMinCost(maze, row, col - 1));
    return minPrevCost + maze[row][col];
}

修复说明 #

1. 新增越界拦截：优先判断row/col是否小于0，返回Integer.MAX_VALUE确保无效路径不会被选中。
2. 自动适配边界场景：第一行单元格调用上方递归时会返回极大值，Math.min会自动选择左侧的有效路径；第一列同理，无需额外编写分支判断。
3. 移除冗余逻辑：原代码中if(row >=0 && col >=0)完全多余，已通过越界判断覆盖。

性能优化（记忆化搜索） #

递归版本会存在大量重复计算，可通过记忆化存储已计算的单元格成本，避免重复递归：

public static int findMinCost(int[][] maze) {
    int rows = maze.length;
    int cols = maze[0].length;
    // 记忆数组，存储已计算完成的单元格最小成本
    Integer[][] memo = new Integer[rows][cols];
    return dfs(maze, rows - 1, cols - 1, memo);
}

private static int dfs(int[][] maze, int row, int col, Integer[][] memo) {
    if (row < 0 || col < 0) {
        return Integer.MAX_VALUE;
    }
    if (row == 0 && col == 0) {
        return maze[row][col];
    }
    // 若已计算过，直接返回缓存值
    if (memo[row][col] != null) {
        return memo[row][col];
    }
    int minPrevCost = Math.min(dfs(maze, row - 1, col, memo), dfs(maze, row, col - 1, memo));
    // 缓存当前单元格的最小成本
    memo[row][col] = minPrevCost + maze[row][col];
    return memo[row][col];
}

内容的提问来源于stack exchange，提问作者Saurabh Pathak