记忆化递归求解最小路径和：如何追踪路径及调整结果存储位置

一、让记忆化DP数组支持路径追踪 #

你用迭代DP能反向追踪路径，核心是每个dp[i][j]记录了从起点到(i,j)的最小和，还能通过对比上方、左方的DP值倒推最优前驱节点。如果你的记忆化递归版本没法追踪路径，大概率是只存了最小和，没记录到达当前位置的最优来源。

解决方法很直接：

• 除了dp数组存最小和，再加一个prev二维数组，每个位置存到达(i,j)的最优前驱坐标（比如从上方来就存(i-1,j)，左方来就存(i,j-1)）。
• 递归计算dp[i][j]时，确定选上方还是左方的路径更优后，同步把对应的前驱坐标存在prev[i][j]里。
• 最后从右下角开始，顺着prev数组往回走，就能把最小路径拉出来。

拿你给的示例grid = [[1,3,1],[1,5,1],[4,2,1]]来说，递归算到(2,2)时，会对比从(1,2)来的路径和（7）和从(2,1)来的（9），选前者，所以prev[2][2] = (1,2)，一步步反向就能得到路径(0,0)→(0,1)→(0,2)→(1,2)→(2,2)。

二、调整递归让结果存在右下角 #

你现在递归从(0,0)开始，结果存在dp[0][0]，说明你的递归状态定义是：dp[i][j]表示从(i,j)走到右下角的最小路径和。要把结果移到右下角，只需要把状态定义反过来：

调整后的递归逻辑：

• 重新定义dp[i][j]：从左上角(0,0)走到(i,j)的最小路径和。
• 终止条件：当i=0且j=0时，dp[0][0] = grid[0][0]。
• 转移规则：
  • 要是i=0（只能从左边走过来）：dp[i][j] = grid[i][j] + dp[i][j-1]
  • 要是j=0（只能从上方走过来）：dp[i][j] = grid[i][j] + dp[i-1][j]
  • 其他情况：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
• 最后直接调用递归函数计算dp[m-1][n-1]，结果就存在右下角的位置里。

给你一段Python伪代码参考：

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[-1]*n for _ in range(m)]  # -1表示未计算

    def dfs(i, j):
        if dp[i][j] != -1:
            return dp[i][j]
        if i == 0 and j == 0:
            dp[i][j] = grid[i][j]
        elif i == 0:
            dp[i][j] = grid[i][j] + dfs(i, j-1)
        elif j == 0:
            dp[i][j] = grid[i][j] + dfs(i-1, j)
        else:
            dp[i][j] = grid[i][j] + min(dfs(i-1, j), dfs(i, j-1))
        return dp[i][j]

    return dfs(m-1, n-1)

这个版本的dp数组和你迭代DP的定义完全一致，既可以直接拿右下角的值当结果，也能和迭代版一样反向追踪路径。

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