§1

题目描述

把规则理清楚:路上有 n+1 个点,编号 0 到 n,每个点有 3 条跑道。obstacles[i] 取值 0 到 3,等于 0 表示点 i 没有障碍,等于 k 表示点 i 的跑道 k 上有一个障碍,同一个点最多只有一条跑道有障碍。青蛙从点 i 沿同一跑道跳到点 i+1,要求点 i+1 的这条跑道没有障碍;它也能在同一个点上侧跳到另一条没有障碍的跑道,两条跑道可以不相邻,一次侧跳算一次。青蛙从点 0 的跑道 2 出发,到达点 n 的任意一条跑道即可,求最少侧跳次数。点 0 和点 n 处任意跑道都没有障碍。

输入 = obstacles = [0,1,2,3,0]　输出 = 2

输入 = obstacles = [0,1,1,3,3,0]　输出 = 0(跑道2全程无障碍,不用侧跳)

输入 = 本节演示 [0,1,2,3,0,2,0]　输出 = 2

§2

思路解析动画文字版

记住三步走:有障碍先封成无穷大、再算 x = 最小代价 + 1、每条通行跑道在直行和侧跳之间取小。起手 f = [1,0,1],扫完取 min(f)。

点0 · 打地基：先填最左边点 0 这一列。青蛙就是从点 0 的跑道 2 出发的,所以站在跑道 2 上一次都没跳,代价是 0。如果它一上来就想换到跑道 1 或跑道 3,那得在原地侧跳一次,所以这两格都是 1。这三个数就是我们的起点,后面每到一个新点,都拿上一列的这三个代价往右推。

点1 · 封障碍：来到点 1,这里跑道 1 上有障碍。先把点 0 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 1 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 1 这个点上是不允许的,先把这条路堵死,免得后面误用它。

点1 · 取最优：现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 2,代价 0。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 0 + 1 = 1。这一个 x 就是「在点 1 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。

点1 · 侧跳更新：最后一步,把 x = 1 拿去和每条通行跑道的直行代价比,取小的留下。通行的跑道2和跑道3直行代价是 0 和 1,都不比 1 大;跑道1被障碍封成 ∞,不参与更新。点 1 这一列最终定格成 ∞ / 0 / 1。

点2 · 封障碍：来到点 2,这里跑道 2 上有障碍。先把点 1 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 2 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 2 这个点上是不允许的,先把这条路堵死,免得后面误用它。

点2 · 取最优：现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 3,代价 1。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 1 + 1 = 2。这一个 x 就是「在点 2 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。

点2 · 侧跳更新：最后一步,把 x = 2 拿去和每条通行跑道的直行代价比,取小的留下。跑道 1 原来的直行代价比 2 大,说明在这个点侧跳过去更省,于是被刷新。点 2 这一列最终定格成 2 / ∞ / 1。

点3 · 封障碍：来到点 3,这里跑道 3 上有障碍。先把点 2 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 3 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 3 这个点上是不允许的,先把这条路堵死,免得后面误用它。

点3 · 取最优：现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 3 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。

点3 · 侧跳更新：最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。跑道 2 原来的直行代价比 3 大,说明在这个点侧跳过去更省,于是被刷新。点 3 这一列最终定格成 2 / 3 / ∞。

点4 · 无障碍：点 4 这里干干净净,一条障碍都没有。那三条跑道都可以从点 3 沿原跑道直行一步过来,代价原样照抄,现在跑道 1、2、3 分别是 2、3、∞。没有需要封死的格子,这一步很轻松。不过直行不一定最省,接下来还要看看在这个点侧跳一下会不会更划算。

点4 · 取最优：现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 4 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。

点4 · 侧跳更新：最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。跑道 3 原来的直行代价比 3 大,说明在这个点侧跳过去更省,于是被刷新。点 4 这一列最终定格成 2 / 3 / 3。

点5 · 封障碍：来到点 5,这里跑道 2 上有障碍。先把点 4 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 2 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 2 这个点上是不允许的,先把这条路堵死,免得后面误用它。

点5 · 取最优：现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 5 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。

点5 · 侧跳更新：最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。通行的跑道1和跑道3直行代价是 2 和 3,都不比 3 大;跑道2被障碍封成 ∞,不参与更新。点 5 这一列最终定格成 2 / ∞ / 3。

点6 · 无障碍：点 6 这里干干净净,一条障碍都没有。那三条跑道都可以从点 5 沿原跑道直行一步过来,代价原样照抄,现在跑道 1、2、3 分别是 2、∞、3。没有需要封死的格子,这一步很轻松。不过直行不一定最省,接下来还要看看在这个点侧跳一下会不会更划算。

点6 · 取最优：现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 6 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。

点6 · 侧跳更新：最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。跑道 2 原来的直行代价比 3 大,说明在这个点侧跳过去更省,于是被刷新。点 6 这一列最终定格成 2 / 3 / 3。

完成 · 答案 2：整张表推满了。末点 6 三条跑道的代价是 2 / 3 / 3,取最小的那个就是答案 2。顺着倒推能还原出这条最省路线:青蛙在点 1 从跑道 2 侧跳到跑道 3,躲过点 2 跑道 2 的障碍继续直行;到点 2 又从跑道 3 侧跳到跑道 1,之后一路沿跑道 1 直行到底。全程正好 2 次侧跳,和表格算出来的 2 完全对上。

三个边界都能手验:有一条跑道全程空则 0 次、障碍逼近需 2 次、只被逼一次则 1 次。

面试三连:三步转移 f=[1,0,1] 起手、贪心最优因无后效性且一次侧跳可达任意道、滚动数组做到 O(1) 空间。

§3

参考代码

from __future__ import annotationsfrom 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)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n)，从左到右扫一遍每个点,每个点只在 3 条固定跑道上做常数次比较和更新,总量跟点数 n 成正比,n 到十万也秒出
空间：O(1)，按峰值算:只用一个长度 3 的滚动数组 f,每个新点只依赖上一个点的三个值,不必开二维表,所以是常数空间

§5

易错点

✗ 错误写法：先算 x = min(f)+1、再把障碍跑道封成无穷

✓ 正确写法：必须先封障碍、再算 x

顺序反了,障碍跑道的旧代价会被当成侧跳源头算进 min,还可能把青蛙更新到一个不能站的跑道上,答案偏小

✗ 错误写法：起手把 f 设成 [0,0,0] 或 [1,1,1]

✓ 正确写法：f 应初始化成 [1,0,1]

青蛙只从跑道 2 出发,站跑道 2 免跳记 0,跑道 1 和跑道 3 得先侧跳一次才到,记 1;设成 [0,0,0] 相当于允许青蛙起步随便选道

✗ 错误写法：C++ / Java 用整型最大值 INT_MAX 当无穷

✓ 正确写法：用 1 左移 30 位这类留余量的哨兵

INT_MAX 再加 1 会溢出成很小的负数,反而变成「最省」,把答案带偏;Python 的浮点 inf 无此问题

面试追问把动画讲成自己的话

追问状态怎么定义,转移是什么?

设 f[j] 为走到当前点、站在跑道 j+1 时的最少侧跳次数,起手 f = [1,0,1]。推到下一个点分三步:有障碍的跑道先置无穷;算 x = min(f) + 1,表示从当前最省跑道侧跳换道的统一代价;每条无障碍跑道取 f[j] 与 x 的较小值。答案是扫完后的 min(f),时间 O(n),空间 O(1)。

追问为什么这样贪心地一遍扫就一定最优?

因为到某个点某条跑道的最少侧跳,只取决于上一个点三条跑道的最少侧跳,是标准的最优子结构,无后效性。侧跳可以一次换到任意跑道,所以「从当前最省跑道跳出去」这个 x 就覆盖了所有换道方案,取 min 保证每格都是全局最优,不需要回头。

追问能不能只用常数空间?

能,而且天然就是。每个新点的三个代价只依赖上一个点的三个代价,用一个长度 3 的滚动数组原地更新即可,空间 O(1)。要留可视化的完整路径时才铺一张 3 行乘 n 列的二维表,那是 O(n),但求答案本身不需要。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 76/108

鸡蛋掉落-两枚鸡蛋

LeetCode 1884 · 中等 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom 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)