算法 - 最長路徑電網益智

所以情況是：
1.有N×N個網格，因此它是一個正方形網格
2.將是將內給予
3.每一個細胞步驟的最高金額電網有一定的價值，這將減少最大步數
4.我們只能移動到右側和下方。
5.起點位於網格的左上方，目標位於網格的右下方。
6.我們需要確定的最長路徑（有步驟至少最大量左邊的一個）
7.如果沒有路徑可能的結果將-1算法 - 最長路徑電網益智

所以目前我已經寫了代碼，將在某些情況下工作，但仍不是最佳的。
我現在正在做的是：
1.檢查下一個正確值和下一個低於值。
2.轉到更大的值。
3.如果最大步數變爲0回溯到前一個單元並移動到另一個方向。
4.如果正確的值和低於的值是相同的，我會檢查下一個單元格後的下一個單元格。

看起來問題是第4點。

這是我第4點代碼：

private static int determineBestNext(int[][] grid, int currentX, int currentY) { 
    int nextRight = 0; 
    int nextBelow = 0; 
    int numberOfRows = grid.length - 1; 
    for(int i=currentX+1;i<numberOfRows-1;i++) { 
     nextRight += grid[currentY][i+1]; 
     if(currentY != numberOfRows) { 
      nextRight += grid[currentY+1][i+1]; 
     } 
    } 
    for(int i=currentY+1;i<numberOfRows-1;i++) { 
     nextBelow = grid[i+1][currentX]; 
     if(currentX != numberOfRows) { 
      nextBelow += grid[i+1][currentX+1]; 
     } 
    } 
    if(nextRight > nextBelow) { 
     return 1; 
    } else if (nextBelow > nextRight) { 
     return 2; 
    } else { 
     return determineBestNext(grid, currentX+1,currentY+1); 
    } 
}

我想回退是當x比y大在Y步進的數量更大，所以機會正確的價值會比X大反之亦然。

你們有別的想法嗎？謝謝！

謝謝！

來源

2014-12-04 Niko Adrianus Yuwono

您可以在O(n^2)找到最佳路徑。我將調用（1,1）左上方的單元格（起點），並將網格（i，j）作爲單元格的值。步驟（i，j）是到達單元（i，j）所需的最小步驟數。

您可以快速識別的關係

steps(i,j) = min(steps(i-1,j), steps(i,j-1)) + grid(i,j) // if i,j > 1

如果i = 1或j = 1或i = j = 1那就更簡單了，因爲那時只有一個可能的路徑。

所以我們要計算steps(N,N)，我們得到steps(N,N) = min(steps(N-1,N), steps(N,N-1)) + grid(N,N)。爲了計算，我們需要steps(N-1,N)和steps(N,N-1)。所以steps(N-1,N) = min(steps(N-2,N), steps(N-1,N-1)) + grid(N-1,N)和steps(N,N-1) = min(steps(N-1,N-1), steps(N,N-2)) + grid(N,N-1)。我們看到，對於每個結果，我們都需要steps(N-1,N-1)的值。這將是一個腰，計算兩次這個值。如果我們只計算一個值並記住該值，則可以保存一個計算結果。這些事情經常發生。

要記住的最好方法是有一個固定的評估順序。下面是一些僞代碼：

function getBestPath(grid, N) 
    steps = new N x N int-array //initialized with 0 

    //first row 
    steps[0][0] = grid[0][0] 
    // only one path to get to (0,0), it's doing nothing 
    for (i = 1; i < N; i++) 
     steps[0][i] = steps[0][i-1] + grid[0][i] 
     // only one path each, just going right 

    //other rows 
    for (row = 1; row < N; row++) 
     steps[row][0] = steps[row-1][0] + grid[row][0] 
     //only one way to get to (row,0), only go down 

     for (i = 1; i < N; i++) 
      steps[row][i] = min(steps[row-1][i], steps[row][i-1]) + grid[row][i] 

    return steps[N-1][N-1]

來源

2014-12-04 09:08:50 user38034

我想你有點誤解我的問題，但你的回答讓我想到一個主意。其實我想得到的並不是最短的路徑，而是可能的最昂貴的路徑 – 2014-12-05 01:44:35

7點讓我覺得你是在一些細節遺漏。

何時不可能？是否假設步驟的數量必須是非負的？

如果不是，那麼路徑總是可能的，並且一個簡單的動態編程O（N^2）算法是可能的，因爲另一個答案告訴你。

您是否試圖通過修改問題並忽略過程中的重要細節來欺騙一些編程測試？

來源

2014-12-04 16:45:08 AnswerCommenteratinator

算法 - 最長路徑電網益智

回答

相關問題