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

Question

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

“极限地铁跑酷”挑战

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

轨道上有从 0 到 N 的点。

在三车道中，某些地方存在某些沙井。现在，为了避开这些沙井，我们的玩家需要侧身跳跃并切换车道，因为如果第 i + 1 点的车道上没有沙井，他就无法从同一条车道上的 i 前往 (i + 1)^th 点.

给定一个长度为 N + 1 的检修孔数组，其中

manholes[i]

告诉我们点 i 的检修孔位于哪条车道上。例如，如果

manholes[2]

= 1，这意味着在火车轨道的点 2 上，车道 1 上存在沙井。

找出我们的玩家为了从火车轨道上的点 0 到达点 N 必须执行的最少变道次数。

注：

如果

manholes[i]

= 0，这意味着对于点 i，任何车道上都不存在沙井。

manholes[0]

和

manholes[N]

始终为 0。

输入格式：

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

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

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

我们的玩家总是从中路开始。

限制：

• manholes.length == n + 1

• 1 <= t <= 100

• 1 <= N <= 5 * 10

  4

• 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。 有什么错误吗？

Answer 1

以下是一些问题：

• 挑战有一个重要的规范：

  我们的玩家总是从中路开始。

  这已经意味着您对

  dp

  的初始化是错误的。进入左车道的成本为 1（一侧台阶）。所以初始化应该是：

  dp[0][0] = dp[0][2] = 1;
  dp[0][1] = 0;
  

• manholes[i] == j + 1

  检查与您在其下方评论中所写内容相反的内容。当车道

  j

  有检修孔时，此条件成立，因此在这种情况下，您应该执行

  else

  块。

• 在

  if

  块中，将 1 添加到外部

  Math.min

  调用的第二个参数。结合您将

  Integer.MAX_VALUE

  存储在某些

  dp

  条目中的事实，您可能会冒着对该值加 1 的风险，该值的计算结果为

  Integer.MIN_VALUE

  ，并且显然会扭曲您的结果。这就是为什么您在其中一项测试中得到 -2147483648 作为输出。我建议不要使用

  Integer.MAX_VALUE

  ，而只使用

  N

  。这是一个足够大的值。

• 您的代码假设即使

  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]));
    }