题目描述
思路解析
一句话答案：LeetCode 1824 最少侧跳次数：青蛙在 3 跑道上逐点前进、遇障碍才侧跳。滚动数组记到当前点各道最少侧跳，每点封障碍成 ∞、取 min+1 当侧跳代价、通行道取小，时间 O(n)、空间 O(1)。
这只青蛙为什么非侧跳不可，题目求的是什么
一条路排着 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 选中。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三步走:有障碍先封成无穷大、再算 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) 空间。
参考代码
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)复杂度
- 时间：O(n)，从左到右扫一遍每个点,每个点只在 3 条固定跑道上做常数次比较和更新,总量跟点数 n 成正比,n 到十万也秒出
- 空间：O(1)，按峰值算:只用一个长度 3 的滚动数组 f,每个新点只依赖上一个点的三个值,不必开二维表,所以是常数空间
易错点
面试追问把动画讲成自己的话
追问状态怎么定义,转移是什么?
追问为什么这样贪心地一遍扫就一定最优?
追问能不能只用常数空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
鸡蛋掉落-两枚鸡蛋
LeetCode 1884 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题