在N * N矩阵中的所有可能的路径 - 蟒蛇

给定一个N * N矩阵，假设你开始在左上角单元格（即0,0）。您可以向右或向下移动，并且必须前往右下角的单元格。获取小于给定值的最大值。例如，假设3 * 3矩阵，给定值为5。

0 1 2 
2 1 2 
3 2 1 

optimal path is 0 -> 1 -> 1 -> 2 -> 1 = 5

我开始使用递归的编码，但答案是不正确的。有什么建议么？

def findAllPaths(currX, currY, path, grid, sum): 
    #print currX, currY 
    if currX == len(grid)-1: 
     i = currY 
     temp = 0 
     while i < len(grid): 
      path = path + str(grid[currX][i]) 
      temp += grid[currX][i] 
      i += 1 
     sum.append(temp) 
     #print 'first loop', sum, path 
     return 
    if currY == len(grid)-1: 
     i = currX 
     temp = 0 
     while i < len(grid): 
      path = path + str(grid[i][currY]) 
      temp += grid[i][currY] 
      i += 1 
     sum.append(temp) 
     #print 'second loop', sum, path 
     return 
    #print currX, currY 
    #path = path + str(grid[currX][currY]) 
    findAllPaths(currX+1,currY,path,grid, sum) 
    findAllPaths(currX, currY+1,path,grid, sum) 

    return sum

来源

2015-09-14 user4812502

您正在追加总和和路径而不删除东西。这是一个递归函数的问题，因为你会尝试一个路径，当你回溯时，你不会删除它们。您或者需要制作副本（cpysum = sum[:]），或者在执行递归操作后删除内容，但没有找到解决方案。

来源

2015-09-14 01:09:43 Foon

我正在使用动态编程来完成任务。通过查找路径的最小值，程序只需要计算当前值+最后一步的最小值。

def minPathSum(grid): 
     res = 0 
     if grid: 
      n,m = len(grid),len(grid[0]) 
      dp = [[0]* m for _ in range(n)] 
      dp[0][0]= grid[0][0] 
      for i in range(1,m): 
       dp[0][i] = dp[0][i-1] + grid[0][i] 
      for i in range(1,n): 
       dp[i][0] = dp[i-1][0]+grid[i][0] 

      for i in range(1,n): 
       for j in range(1,m): 
        dp[i][j] = grid[i][j] 
        dp[i][j] += min(dp[i][j-1],dp[i-1][j]) 

      res = dp[-1][-1] 
     return res 

grid = [ [0,1,2],[2 ,1 ,2],[3 ,2 ,1]] 
print(minPathSum(grid))

来源

2015-09-14 02:04:23 galaxyan

在N * N矩阵中的所有可能的路径 - 蟒蛇

回答

相关问题