python - 为什么将 DO 添加到我的递归中会使其停止正常工作？

Question

有人可以告诉我为什么这两个代码给出不同的输出吗？它们不是相同的代码但具有两种不同的实现(一种是暴力破解，另一种是使用动态编程)。

程序描述:给定一个充满非负数的 m x n 网格，找到一条从左上角到右下角的路径，使沿该路径的所有数字的总和最小。

def minPathSum_dp(grid):
        def dfs(i, j, pathSum):
            if (i, j) in dp:
                return dp[(i, j)]
            
            if i == len(grid)-1 and j == len(grid[i])-1:
                return pathSum + grid[i][j]

            if i == len(grid)-1:
                return dfs(i, j+1, pathSum + grid[i][j])
            
            if j == len(grid[i])-1:
                return dfs(i+1, j, pathSum + grid[i][j])
            
            path1 = dfs(i+1, j, pathSum + grid[i][j])
            path2 = dfs(i, j+1, pathSum + grid[i][j])
            dp[(i, j)] = min(path1, path2)
            return dp[(i, j)]
        
        dp = {}
        return dfs(0, 0, 0) 

def minPathSum_bf(grid):
        def dfs(i, j, pathSum):          
            if i == len(grid)-1 and j == len(grid[i])-1:
                return pathSum + grid[i][j]
            
            if i == len(grid)-1:
                return dfs(i, j+1, pathSum + grid[i][j])
            
            if j == len(grid[i])-1:
                return dfs(i+1, j, pathSum + grid[i][j])
            
            path1 = dfs(i+1, j, pathSum + grid[i][j])
            path2 = dfs(i, j+1, pathSum + grid[i][j])
            return min(path1, path2)
        
        return dfs(0, 0, 0) 

grid = [[1,4,8,6,2,2,1,7],[4,7,3,1,4,5,5,1],[8,8,2,1,1,8,0,1],[8,9,2,9,8,0,8,9],[5,7,5,7,1,8,5,5],[7,0,9,4,5,6,5,6],[4,9,9,7,9,1,9,0]]

UPDATED: WORKING SOLUTION

def minPathSum(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if (i, j) in dp:
                return dp[(i, j)]
            
            if i == len(grid)-1 and j == len(grid[i])-1:
                return grid[i][j]
            
            if i == len(grid)-1:
                dp[(i, j)] = grid[i][j] + dfs(i, j+1)
                return dp[(i, j)]
            
            if j == len(grid[i])-1:
                dp[(i, j)] = grid[i][j] + dfs(i+1, j)
                return dp[(i, j)]
            
            path1 = grid[i][j] + dfs(i+1, j)
            path2 = grid[i][j] + dfs(i, j+1)
            dp[(i, j)] = min(path1, path2)
            return dp[(i, j)]
        
        dp = {}
        return dfs(0, 0)

print(minPathSum_dp(grid))
print(minPathSum_bf(grid))

Answer 1

(一个快速的术语说明 - 在我看来，你在这里所做的事情比动态编程更接近内存，因为你是自上而下而不是自下而上计算事物。)

您的递归函数有三个参数。前两个是“我现在在哪里？”第三个问题是“到目前为止，我一路走来的总和是多少？”例如，调用 dfs(row, col, 137)如果您位于 (row, col) 并且当前路径的成本为 137，并且调用 dfs(row, col, 42)，则为您提供可以达到的最佳成本。如果当前路径的成本为 42，则为您提供成本。

但是，您的 DP/内存表仅以前两个参数为关键。这意味着您在位置(行，列)写下的值需要同时是 dfs(row, col, 137) 的答案。和dfs(row, col, 42) 。但这显然行不通。

从技术上讲，您可以通过让 DP/内存表写下由所有三个参数键入的答案来解决此问题。但是，这不会使事情运行得很快，因为您不太可能最终以相同的前缀和对网格中的同一位置进行两次或多次递归调用。

解决此问题的更正确方法是更改​​递归策略，以便您不需要到当前点的路径成本的第三个参数。通过使用该参数，每个递归调用都必须了解将其发送到那里的特定调用链。相反，看看是否可以找到一种方法，使递归函数只接受 (row, col) 对并返回从该点到目的地的最佳成本。一旦你完成了这个工作，你就可以添加内存，它会工作得很好。