算法 - 最长路径网格拼图

Question

所以情况是：
1.有NxN网格，所以它是一个方形网格
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 中的步数更大，因此机会 Right 值将大于 X，反之亦然。

你们有别的想法吗？谢谢！

谢谢！

Answer 1

您可以在 O(n^2) 中找到最佳路径。我将调用 (1,1( 左上角单元格(起点(，grid(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]

Answer 2

第

7点让我觉得你错过了一些细节。

什么时候没有路径可能？步长量需要为非负数的假设是否为负数？

如果不是，那么路径总是可能的，一个简单的动态规划 O(N^2( 算法是可能的，正如另一个答案告诉你的那样。

您是否试图通过修改问题并错过过程中的重要细节来欺骗某些编程测试？