递归+记忆化实现最小代价路径出错，请求排查问题

你的代码在无记忆化时能正确输出，是因为它会穷举所有可能的路径，最终找到代价最小的那条。但添加记忆化后出错，核心问题在于记忆化的逻辑不适用于四方向移动的网格最短路径问题：

记忆化失效的原因 #

1. 过早存储非最优值：你的代码采用深度优先搜索（DFS）的顺序探索路径，第一次计算某个单元格(row, col)到终点的代价时，可能走的是一条较优但不是最优的路径。一旦将这个非最优值存入mem数组，后续再遇到该单元格时，会直接返回已存储的值，不会再探索更优的路径。
2. 记忆化假设不成立：对于只能向右/向下移动的网格问题，每个单元格的最优代价仅依赖于后续单元格，记忆化是有效的。但四方向移动时，单元格可以通过多种路径到达，后续可能发现更优的路径到该单元格，进而得到更小的终点代价——而你的代码无法更新已记忆的旧值。

以测试用例为例，代码可能先探索左侧列的长路径，将这些单元格的代价记忆为较高的值，后续探索中间含1的最优路径时，会因依赖已记忆的高代价单元格，最终得到错误的37。

由于网格中所有单元格的代价都是正数（无负权环），最适合的解法是Dijkstra算法，它能保证每次优先探索当前代价最小的路径，确保找到全局最优解。

修正后的Java代码 #

import java.util.PriorityQueue;

public class MinimumCostPath {
    public int minimumCostPath(int[][] grid) {
        int n = grid.length;
        int[][] minCost = new int[n][n];
        
        // 初始化所有单元格的最小代价为无穷大
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                minCost[i][j] = Integer.MAX_VALUE;
            }
        }
        minCost[0][0] = grid[0][0];
        
        // 优先队列：存储[当前总代价, 行, 列]，按代价升序排列
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{grid[0][0], 0, 0});
        
        // 四方向移动数组
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentCost = current[0];
            int row = current[1];
            int col = current[2];
            
            // 到达终点，直接返回当前代价
            if (row == n - 1 && col == n - 1) {
                return currentCost;
            }
            
            // 如果当前代价大于已知的最小代价，跳过该路径（已找到更优路径）
            if (currentCost > minCost[row][col]) {
                continue;
            }
            
            // 探索四个方向
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                    int newTotalCost = currentCost + grid[newRow][newCol];
                    // 如果新路径代价更小，更新并加入优先队列
                    if (newTotalCost < minCost[newRow][newCol]) {
                        minCost[newRow][newCol] = newTotalCost;
                        pq.add(new int[]{newTotalCost, newRow, newCol});
                    }
                }
            }
        }
        
        // 理论上不会执行到这里（网格连通）
        return minCost[n-1][n-1];
    }
}

代码说明 #

1. 优先队列：始终弹出当前总代价最小的路径，确保我们优先探索最可能成为最优解的路径。
2. 最小代价矩阵：记录每个单元格到起点的最小总代价，每次发现更优路径时更新。
3. 剪枝逻辑：如果当前路径的代价已经大于已知的最小代价，直接跳过，避免无效探索。

测试该代码会返回正确的30。

内容的提问来源于stack exchange，提问作者Elias El hachem