在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矩陣中的所有可能的路徑 - 蟒蛇

回答

相關問題