Can someone please tell me why the two codes give different outputs. Aren't they the same code with two different implementations (one is brute force and the other one is using Dynamic Programming).

Program Description: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

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))

推荐答案

(A quick terminology note - what you’re doing here seems to me to be closer to memoization than dynamic programming, since you’re computing things top-down rather than bottom-up.)

Your recursive function has three parameters. The first two are “where am I right now?” The third is “what is the sum along the path that’s taken me here so far?” So, for example, calling dfs(row, col, 137) gives you the best cost you can reach if you are at (row, col) and the cost of the current path is 137, and calling dfs(row, col, 42) gives you the cost if your current path has cost 42.

However, your DP/memoization table is only keyed on the first two parameters. This means that the value you’re writing down at position (row, col) would need to be the answer for both dfs(row, col, 137) and dfs(row, col, 42). But that’s clearly not going to work.

You could technically fix this by having your DP/memoization table write down answers keyed by all three parameters. However, that’s not going to make things run quickly, since you’re unlikely to end up with two or more recursive calls being made to the same position in the grid with the same prefix sum.

The more proper way to fix this is to change your recursive strategy so that you don’t need that third parameter of the path cost up to your current point. By having that parameter, each recursive call has to be aware of the specific call chain that got it there. Instead, see if you can find a way to make the recursive function just take in a (row, col) pair and return the best cost from that point to the destination. Once you’ve gotten that working, you can add in memoization and it’ll work just fine.

Python相关问答推荐

根据传递给这些元素的函数的返回值更改 numpy 数组的元素

Matplotlib 图表没有动画/Pandas 数据问题

从列表的Pandas 列创建堆栈

Pandas:创建 Origin-Destination 矩阵,将destination-of-destination 保持在同一行

在 Altair 折线图和面积图中更改步骤的宽度

不能从另一个目录执行 Python 导入

tkinter 中的计算器应用程序问题 - Python

在排序数组中查找目标范围的时间复杂度 - 这个解决方案在最坏的情况下是 O(N) 吗?

使用 Google Cloud 函数触发 Cloud Composer

如果包含缺失值,如何在 Python 中创建虚拟变量?

没有循环的矩数组表相乘

有没有办法计算数据框中至少包含一个“1”的所有行,判断多个命名列?

Pandas 数组过滤 NaN 并保留组中的第一个值

在 python 中使用 any 函数时,有没有办法查看找到了哪个列表项?

正则表达式 Python,除了字母序列

如何使用复杂的自定义 id 作为 Select 器在 pytest 中运行单个测试?

如何在python中复制文件夹和文件

如何从 parseAction 获取 pyparsing 解析器的值

解决 GEKKO 中的后退地平线控制

多个矩阵的加权和