解决编码问题的替代方法

Question

我尝试使用动态编程解决这个问题，但没有得到预期的结果。

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

轨道上有从 0 到 N 的点。 在三车道中，某些地方存在某些沙井。现在，为了避开这些沙井，我们的玩家需要侧身跳跃并切换车道，因为如果第 i + 1 点的车道上没有沙井，他就无法从同一条车道上的 i 到第 (i + 1) 个点。 给定一个长度为 N + 1 的数组人孔，其中 manholes[i] 告诉我们点 i 的人孔位于哪条车道上。例如，如果 manholes[2] = 1，这意味着在火车轨道的点 2 上，车道 1 上存在沙井。

找出我们的玩家为了从火车轨道上的点 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 。

我的方法失败了，我想用替代方法来解决问题。预先感谢

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

  ，并且显然会扭曲您的结果。我建议不要使用

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