使用动态规划解决Limited Subway Surfer挑战时结果异常，求排查

问题描述 #

Nidhi制作了Subway Surfer的改版游戏：轨道包含N+1个点（编号0到N），共3条车道。部分点的特定车道存在检修孔（manhole），玩家无法在有检修孔的车道停留或移动。manholes数组中，manholes[i]表示第i点检修孔所在的车道（1/2/3），0表示该点无检修孔；manholes[0]和manholes[N]始终为0。玩家从0点的中间车道出发，求从0点到N点的最少变道次数。

输入输出示例 #

输入：

4
0 1 2 3 0

输出：2

错误代码 #

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. 初始化错误 #

玩家初始位于0点的中间车道（对应数组索引1），因此只有dp[0][1]应设为0（无需变道）；dp[0][0]和dp[0][2]初始不可达，应设为Integer.MAX_VALUE，而非0。

2. 条件判断逻辑颠倒 #

manholes[i] == j+1表示第i点的j车道存在检修孔，此时玩家无法在该车道停留，dp[i][j]应设为Integer.MAX_VALUE。而你的代码中错误地将这种情况视为可停留的条件，完全搞反了逻辑。正确的判断应为：如果manholes[i] == j+1，则该车道不可达；否则可以停留并计算最小变道次数。

3. 状态转移未处理溢出问题 #

当dp[i-1][k]为Integer.MAX_VALUE时，dp[i-1][k] + 1会溢出为Integer.MIN_VALUE（即你得到的-2147483648），导致结果错误。需要先判断前置状态是否可达，跳过不可达的路径。

修正后的代码 #

public int minLaneChanges(int[] manholes) {
    int N = manholes.length - 1;
    int[][] dp = new int[N + 1][3];
    
    // 初始化：从中间车道（索引1）出发，其余车道初始不可达
    dp[0][0] = Integer.MAX_VALUE;
    dp[0][1] = 0;
    dp[0][2] = Integer.MAX_VALUE;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < 3; j++) {
            // 当前车道j在i点有检修孔，不可达
            if (manholes[i] == j + 1) {
                dp[i][j] = Integer.MAX_VALUE;
                continue;
            }
            
            int min = Integer.MAX_VALUE;
            // 遍历上一个点的所有车道
            for (int k = 0; k < 3; k++) {
                if (dp[i-1][k] == Integer.MAX_VALUE) {
                    continue; // 跳过不可达的前置状态
                }
                // 计算变道次数：同车道不变道，不同车道加1
                int cost = dp[i-1][k] + (k == j ? 0 : 1);
                if (cost < min) {
                    min = cost;
                }
            }
            dp[i][j] = min;
        }
    }

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

内容的提问来源于stack exchange，提问作者user22921484