最少侧跳的次数

2021-04-11

5728. 最少侧跳次数

给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个点，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道出发，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。

这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处侧跳到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。

这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

示例 1：

输入：obstacles = [0,1,2,3,0]
输出：2 
解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。

示例 2：

1
2
3

输入：obstacles = [0,1,1,3,3,0]
输出：0
解释：跑道 2 没有任何障碍，所以不需要任何侧跳。

示例 3：

1
2
3

输入：obstacles = [0,2,1,0,3,0]
输出：2
解释：最优方案如上图所示。总共有 2 次侧跳。

提示：

obstacles.length == n + 1
1 <= n <= 5 * 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

记忆化搜索

class Solution {
    public int minSideJumps(int[] obstacles) {
        // 每一个位置有三个状态
        int n = obstacles.length;
        dp = new int[n][4];
        return Math.min(f(obstacles, n - 2, 2), Math.min(f(obstacles, n - 2, 1), f(obstacles, n - 2, 3)));
    }

    int dp[][];

    public int f(int[] obs, int index, int road) {
        if (index == 0) {
            if (road == 2) return 0;
            else return 1;
        }
        if (dp[index][road] != 0) return dp[index][road];
        int res = 0;
        // 当前位置没有障碍物
        if (obs[index] == 0) {
            int n1, n2;
            if (road == 1) {
                n1 = 2;
                n2 = 3;
            } else if (road == 2) {
                n1 = 1;
                n2 = 3;
            } else {
                n1 = 1;
                n2 = 2;
            }
            res = Math.min(f(obs, index - 1, road), Math.min(f(obs, index - 1, n1), f(obs, index - 1, n2)) + 1);

        } else if (obs[index] == 1) {
            // 障碍物在1这条路上
            if (road == 1) {
                res = Integer.MAX_VALUE / 2;
            } else if (road == 2) {
                res = Math.min(f(obs, index - 1, road), f(obs, index - 1, 3) + 1);
            } else {
                res = Math.min(f(obs, index - 1, road), f(obs, index - 1, 2) + 1);
            }

        } else if (obs[index] == 2) {
            // 障碍物在2这条路上
            if (road == 1) {
                res = Math.min(f(obs, index - 1, road), f(obs, index - 1, 3) + 1);
            } else if (road == 2) {
                res = Integer.MAX_VALUE / 2;
            } else {
                res = Math.min(f(obs, index - 1, road), f(obs, index - 1, 1) + 1);
            }
        } else {
            // 障碍物在3这条路上
            if (road == 1) {
                res = Math.min(f(obs, index - 1, road), f(obs, index - 1, 2) + 1);
            } else if (road == 2) {
                res = Math.min(f(obs, index - 1, road), f(obs, index - 1, 1) + 1);
            } else {
                res = Integer.MAX_VALUE / 2;
            }
        }
        dp[index][road] = res;
        return res;
    }
}

自底向上的动态规划


class Solution {
    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length;
        int[][] dp=new int[n][3];
        dp[0][0]=1;
        dp[0][2]=1;
        
        for(int i=1;i<n;++i){
            if(obstacles[i]==1){    
                dp[i][0]=Integer.MAX_VALUE-1;
                dp[i][1]=Math.min(dp[i-1][1],dp[i-1][2]+1);
                dp[i][2]=Math.min(dp[i-1][2],dp[i-1][1]+1);                
            }else if(obstacles[i]==2){
                dp[i][1]=Integer.MAX_VALUE-1;
                dp[i][0]=Math.min(dp[i-1][0],dp[i-1][2]+1);
                dp[i][2]=Math.min(dp[i-1][2],dp[i-1][0]+1);                
            }else if(obstacles[i]==3){
                dp[i][2]=Integer.MAX_VALUE-1;
                dp[i][0]=Math.min(dp[i-1][0],dp[i-1][1]+1);
                dp[i][1]=Math.min(dp[i-1][1],dp[i-1][0]+1);                
            }else{
                dp[i][0]=Math.min(dp[i-1][0],Math.min(dp[i-1][1],dp[i-1][2])+1);
                dp[i][1]=Math.min(dp[i-1][1],Math.min(dp[i-1][0],dp[i-1][2])+1);
                dp[i][2]=Math.min(dp[i-1][2],Math.min(dp[i-1][0],dp[i-1][1])+1);
            }            
        }
        
        return Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2]));
    }
}

作者：gao-he-jin
链接：https://leetcode-cn.com/problems/minimum-sideway-jumps/solution/javadong-tai-gui-hua-by-gao-he-jin-guw6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。