有限地铁跑酷挑战中动态编程的错误输出-解网

问：

我尝试使用动态编程解决此代码挑战，但我没有得到预期的结果。

“有限的地铁冲浪者”挑战

Nidhi 创建了 Subway Surfer 游戏的替代版本。她的新版本不是在无限长度的火车轨道上，而是限制在长度为 N + 1 的轨道上。就像原版游戏一样，这个替代版本也有三条车道。

轨道上有从 0 到 N 的点。

在三条车道中，在某些地方，存在某些检修孔。现在，为了避开这些沙井，我们的玩家需要侧身跳跃并切换车道，因为如果 i + 1 点的车道上没有沙井，他就不能在同一条车道上从 i 到（i + 1） ^点。

你得到一个长度为 N + 1 的数组检修孔，其中告诉我们点 i 的人孔位于哪条车道上。例如，如果 = 1，则表示在火车轨道的第 2 点上，车道 1 上存在检修孔。manholes[i]manholes[2]

找出我们的玩家必须执行的最小变道次数，以便从火车轨道上的点 0 到达点 N。

注意：

如果 = 0，则表示对于点 i，任何车道上都不存在检修孔。manholes[i]

manholes[0]并且始终为 0。manholes[N]

输入格式：

输入的第一行包含整数 T，表示测试用例的数量。

每个测试用例的第一行包含整数 N。

每个测试用例的第二行包含 N + 1 个空格分隔的整数，表示检修孔[i]。

我们的球员总是从中路开始。

约束：

manholes.length == n + 1

1 <= t <= 100

1 <= N <= 5 * 10⁴

0 <= manholes[i] <= 3

manholes[0] == manholes[n] == 0

输出格式：

从点 0 到 N 达到的最小车道变换次数。

示例输入：
4
0 1 2 3 0
示例输出：
2
解释：

我们的玩家遵循的最佳路径如下图所示：

很明显，为了以最佳方式从点 0 到达点 N，我们的玩家必须至少改变两次车道。

尝试

我对上述挑战的代码是：

    public int minLaneChanges(int[] manholes) {
        int N = manholes.length - 1;
        int[][] dp = new int[N + 1][3];

        // Set initial values
        dp[0][0] = dp[0][2] = 0;

        // Iterate over the points
        for (int i = 1; i <= N; i++) {
            // Iterate over the lanes
            for (int j = 0; j < 3; j++) {
                if (manholes[i] == 0 || manholes[i] == j + 1) {
                    // Manhole on a different lane, find minimum lane change
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + 1);
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        return Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]));
        
    }

我的方法是从第一行开始，然后从第二行迭代每一行和每一列。如果我看到障碍物/检修孔，我将当前位置值设置为最大值，否则我将当前值设置为最小值（同一车道上的上一个位置，最小（其他车道的前一个位置）+1）。

最后，我在最后一行返回 min。

我的方法失败了。对于上面的示例输入，它输出 -2147483648。错误是什么？

Java 算法数据结构动态规划

挑战赛有以下重要规范：

我们的球员总是从中路开始。

这已经意味着你的初始化是错误的。进入左侧车道的费用为 1（一侧台阶）。所以初始化应该是：dp
```
dp[0][0] = dp[0][2] = 1;
dp[0][1] = 0;
```
manholes[i] == j + 1检查与您在它下方的评论中写的内容相反。当车道有检修孔时，这种情况为真，因此在这种情况下，您应该执行阻塞。jelse
在块中，将 1 添加到外部调用的第二个参数。再加上您存储了某些条目，您可能会将该值加 1，这会计算结果并明显扭曲您的结果。这就是为什么您在其中一个测试中将 -2147483648 作为输出的原因。我建议不要使用，而只是 .这是一个足够大的值。ifMath.minInteger.MAX_VALUEdpInteger.MIN_VALUEInteger.MAX_VALUEN
您的代码假定即使有检修孔，也可以进行车道切换（在上一行）。dp[i-1][j]

没问题，但您可以将数组减少到一个维度（有三个条目）。您可以以增量方式更新相同的三元组，以将其与当前点对齐。dp

以下是建议的更新代码：

    public int minLaneChanges(int[] manholes) {
        int N = manholes.length - 1;
        int[] dp = new int[]{1, 0, 1}; // Initialise that player is in middle

        // Iterate over the points
        for (int i = 1; i <= N; i++) {
            // If there is a manhole, invalidate paths that arrive there:
            if (manholes[i] > 0) dp[manholes[i] - 1] = N;
            // Get the best lane at this point 
            int best = Math.min(dp[0], Math.min(dp[1], dp[2]));
            // Check if non-best lanes (without hole) can be improved
            //    by jumping sideways from the best lane
            for (int j = 0; j < 3; j++) {
                if (j + 1 != manholes[i]) dp[j] = Math.min(dp[j], best + 1);
            }
        }
        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }

0赞 lal khan 12/3/2023 #2

代码中的问题源于动态规划矩阵（dp）的初始化。鉴于玩家始终从中间对线开始，dp[0][0] 和 dp[0][2] 的初始值应设置为 1 而不是 0。此外，条件检修孔**[i] == j + 1** 应更改为检修孔**[i] == j + 1**，以正确识别带有检修孔的车道。最后，使用 Integer.MAX_VALUE 可能会导致意外结果;请考虑改用足够大的值，如 N。下面是代码片段的修订版本，可解决这些问题：

    public int minLaneChanges(int[] manholes) {
    int N = manholes.length - 1;
    int[][] dp = new int[N + 1][3];

    // Set initial values
    dp[0][0] = dp[0][2] = 1;
    dp[0][1] = 0;

    // Iterate over the points
    for (int i = 1; i <= N; i++) {
        // Iterate over the lanes
        for (int j = 0; j < 3; j++) {
            if (manholes[i] == j + 1) {
                // Manhole on the same lane, find minimum lane change
                dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + 1);
            } else {
                dp[i][j] = N;
            }
        }
    }

    return Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]));
}

这种修改后的方法应符合问题的要求，并改进玩家到达目的地所需的变道计算。

上一个：何时选择红黑树而不是 AVL 树？

下一个：为两个节点查找共同祖先时出现问题

有限地铁跑酷挑战中动态编程的错误输出

Wrong output with dynamic programming on Limited Subway Surfer challenge

“有限的地铁冲浪者”挑战

注意：

输入格式：

约束：

输出格式：

示例输入：

示例输出：

解释：

尝试

评论