最少侧跳次数 图解题解

这只青蛙为什么非侧跳不可，题目求的是什么

一条路排着 n+1 个点，编号 0 到 n，每个点横摆 3 条跑道。obstacles[i] 为 0 表示点 i 没障碍，为 k 表示跑道 k 上有障碍，一个点最多堵一条道。青蛙从点 0 的跑道 2 出发，沿同一条道能跳到下个点（那点这条道没障碍才行），也能原地侧跳到另一条空道，一次算一跳、不挨着也行。走到点 n 任意一条道即到，问最少侧跳几次；点 0、点 n 三条道都干净。

每个点都能换道，为什么不能把所有跳法试一遍

每个点上除了直行还有两种换道，n 个点连乘走法是指数级，点数上千就试不完；而『从某点某道往后走的最省跳法』被无数条前缀反复重算。这就该用动态规划（把『到某点、停某道最少跳几次』这类小问题的答案算一次存住、后面直接取用，不再重算）。

三条跑道的代价怎么用一个长度 3 的数组记住

用长度 3 的数组 f 当状态（记录当前局面的关键数，这里是三条道各自的代价）：f[0]、f[1]、f[2] 表示走到当前点、停在跑道 1、2、3 上时一路最少侧跳几次。点 0 上青蛙站跑道 2、没跳过，f[1]=0；改停另两道得先原地侧跳一次，f[0]、f[2] 都是 1，f 起手 [1,0,1]。

封障碍、取 min 加一、每道取小，这三步凭什么对

从上一个点推到当前点分三步，就是这题的转移（拿上个点的三个代价推出当前点的三个）：一，当前点哪条道有障碍就把那条 f 封成 ∞（大到不可能被选中的数），青蛙停不到障碍上；二，算侧跳统一代价 x = min(f) + 1，从当前最省的道侧跳到哪条都只多花 1 次；三，每条没障碍的道拿直行代价和 x 取小。

拿 [0,1,2,3,0] 把三条跑道的代价逐点推出来

起手点 0：f = [1,0,1]。点 1 障碍在跑道 1：封 f[0] 成 ∞ 得 [∞,0,1]；x = 0 + 1 = 1，通行的跑道 2、跑道 3 代价 0 和 1 都不比 1 大，定格 [∞,0,1]。点 2 障碍在跑道 2：封 f[1] 得 [∞,∞,1]；x = 1 + 1 = 2，跑道 1 的 ∞ 刷成 2，定格 [2,∞,1]。点 3 障碍在跑道 3：封 f[2] 得 [2,∞,∞]；x = 2 + 1 = 3，跑道 2 刷成 3，定格 [2,3,∞]。点 4 没障碍：x = 2 + 1 = 3，三条道代价 2、3、∞，跑道 3 的 ∞ 刷成 3，定格 [2,3,3]。取 min(2,3,3) = 2 就是答案。

封障碍要是排到算 x 之后，整列为什么会算歪

封障碍要是挪到算 x 后面，障碍道没清掉的旧代价会混进 min，偏小的 x 一路污染后面每条道，整列全塌。全程从左到右扫一遍，每个点只做常数次比较更新，时间 O(n)（大 O 记号，描述数据规模变大时操作次数怎么涨）；每个新点只用得上上一个点的三个代价，一个长度 3 的滚动数组（只留最近用得到的那几项、循环覆盖旧值）就够，空间 O(1)。起手写成全 0 是另一个常见反写——那等于让青蛙零代价凭空站上任意道。哨兵（哨兵=占位用的假极大值）也有讲究：C++、Java 别用 INT_MAX，加 1 溢出成负数反被 min 选中。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        f = [1, 0, 1]
        for v in obstacles[1:]:
            for j in range(3):
                if v == j + 1:
                    f[j] = inf
                    break
            x = min(f) + 1
            for j in range(3):
                if v != j + 1:
                    f[j] = min(f[j], x)
        return min(f)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        const int inf = 1 << 30;
        int f[3] = {1, 0, 1};
        for (int i = 1; i < obstacles.size(); ++i) {
            for (int j = 0; j < 3; ++j) {
                if (obstacles[i] == j + 1) {
                    f[j] = inf;
                    break;
                }
            }
            int x = min({f[0], f[1], f[2]}) + 1;
            for (int j = 0; j < 3; ++j) {
                if (obstacles[i] != j + 1) {
                    f[j] = min(f[j], x);
                }
            }
        }
        return min({f[0], f[1], f[2]});
    }
};

Java

import java.util.*;
class Solution {
    public int minSideJumps(int[] obstacles) {
        final int inf = 1 << 30;
        int[] f = {1, 0, 1};
        for (int i = 1; i < obstacles.length; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (obstacles[i] == j + 1) {
                    f[j] = inf;
                    break;
                }
            }
            int x = Math.min(f[0], Math.min(f[1], f[2])) + 1;
            for (int j = 0; j < 3; ++j) {
                if (obstacles[i] != j + 1) {
                    f[j] = Math.min(f[j], x);
                }
            }
        }
        return Math.min(f[0], Math.min(f[1], f[2]));
    }
}