算法 - 最长路径网格拼图

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 中的步数更大，因此正确值的机会将大于 X，反之亦然。

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

谢谢!

Answer 1

您可以在 O(n^2) 中找到最佳路径。我将 (1,1) 称为左上角的单元格(起点)，而 grid(i,j) 将是该单元格的值。 steps(i,j) 是到达 cell(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)) + 网格(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) 和 步数(N,N-1) = min(步数(N-1,N-1),步数(N,N-2)) + 网格(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]