1824. 最少侧跳次数

1824. 最少侧跳次数

题解

1. dp 数组： dp[i] 表示 到 第i条赛道的最小侧跳次数

class Solution {
   public int minSideJumps(int[] obstacles) {
        int INF = (int) 0x3f3f3f3f;
        int len = obstacles.length;
        int[] dp = new int[4];
        // 从赛道2开始
        dp[1] = 1;
        dp[3] = 1;
        for (int i = 1; i < len; i++) {
            int obstacle = obstacles[i];
            // 该点不可达
            dp[obstacle] = INF;
            for (int j = 1; j < 4; j++) {
                // obstacle条赛道此时是不可达的，不更新该赛道
                // 该赛道 只能从 该赛道的i-1位更新过来，或者从第i位的其他赛道 + 1 更新过来
                if (obstacle!=1) {
                    dp[1] = Math.min(dp[j] + 1, dp[1]);
                }
                if (obstacle!=2) {
                    dp[2] = Math.min(dp[j] + 1, dp[2]);
                }
                if (obstacle!=3) {
                    dp[3] = Math.min(dp[j] + 1, dp[3]);
                }
            }
        }
        // 取3条赛道最小值
        return Math.min(dp[1], Math.min(dp[2], dp[3]));
    }
}