算法 - 最长路径电网益智

所以情况是：
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

算法 - 最长路径电网益智

回答

相关问题