题目描述

给你一个长度为 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 处的任一跑道都不会有障碍。

样例

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

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

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

限制

• obstacles.length == n + 1
• 1 <= n <= 5 * 10^5
• 0 <= obstacles[i] <= 3
• obstacles[0] == obstacles[n] == 0

算法

(动态规划) $O(n)$

1. 设状态 $f(i, j)$ 表示在点 $i$ 的跑道 $j$ 时的最少侧跳次数，其中 $i$ 的取值范围为 $[0, n]$，$j$ 的取值范围为 $[0, 2]$。
2. 初始时，$f(0, 1) = 0$，$f(0, 0) = f(0, 2) = 1$，其余待定。
3. 转移时，对于每个点 $i$，
   • 如果点 $i$ 没有障碍，则 $f(i, j) = f(i - 1, j)$。考虑侧跳，$f(i, j) = \min(f(i, j), m + 1)$，其中 $m$ 为 $f(i, j)$ 中的最小值。
   • 如果点 $i$ 有障碍，假设障碍为 $j_0$。则 $f(i, j_0) = +\infty$，其余 $j \neq j_0$，有 $f(i, j) = f(i - 1, j)$。考虑侧跳，当 $j \neq j_0$ 时，$f(i, j) = \min(f(i, j), m + 1)$，其中 $m$ 为 $f(i, j)$ 中的最小值。
4. 最终答案为 $\min(f(n, 0), f(n, 1), f(n, 2))$。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 可以将第一维优化掉，故总空间复杂度为常数。

C++ 代码

class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        const int n = obstacles.size() - 1;
        const int INF = 1000000000;
        vector<int> f(3, INF);

        f[1] = 0;
        f[0] = f[2] = 1;

        for (int i = 1; i <= n; i++) {
            int mi = INF;
            for (int j = 0; j < 3; j++)
                if (j != obstacles[i] - 1)
                    mi = min(mi, f[j]);

            for (int j = 0; j < 3; j++)
                if (j != obstacles[i] - 1)
                    f[j] = min(f[j], mi + 1);
                else
                    f[j] = INF;
        }

        return min(f[0], min(f[1], f[2]));
    }
};