[英] Why does adding DP to my recursion make it stop working correctly?
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))
