LeetCode 1824中等动态规划
最少侧跳次数 图解题解
这道题到底在问什么
把规则理清楚:路上有 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
最优解：一步一步想明白
- 3记住三步走:有障碍先封成无穷大、再算 x = 最小代价 + 1、每条通行跑道在直行和侧跳之间取小。起手 f = [1,0,1],扫完取 min(f)。
- 4先填最左边点 0 这一列。青蛙就是从点 0 的跑道 2 出发的,所以站在跑道 2 上一次都没跳,代价是 0。如果它一上来就想换到跑道 1 或跑道 3,那得在原地侧跳一次,所以这两格都是 1。这三个数就是我们的起点,后面每到一个新点,都拿上一列的这三个代价往右推。
- 5来到点 1,这里跑道 1 上有障碍。先把点 0 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 1 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 1 这个点上是不允许的,先把这条路堵死,免得后面误用它。
- 6现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 2,代价 0。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 0 + 1 = 1。这一个 x 就是「在点 1 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。
- 7最后一步,把 x = 1 拿去和每条通行跑道的直行代价比,取小的留下。通行的跑道2和跑道3直行代价是 0 和 1,都不比 1 大;跑道1被障碍封成 ∞,不参与更新。点 1 这一列最终定格成 ∞ / 0 / 1。
- 8来到点 2,这里跑道 2 上有障碍。先把点 1 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 2 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 2 这个点上是不允许的,先把这条路堵死,免得后面误用它。
- 9现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 3,代价 1。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 1 + 1 = 2。这一个 x 就是「在点 2 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。
- 10最后一步,把 x = 2 拿去和每条通行跑道的直行代价比,取小的留下。跑道 1 原来的直行代价比 2 大,说明在这个点侧跳过去更省,于是被刷新。点 2 这一列最终定格成 2 / ∞ / 1。
- 11来到点 3,这里跑道 3 上有障碍。先把点 2 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 3 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 3 这个点上是不允许的,先把这条路堵死,免得后面误用它。
- 12现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 3 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。
- 13最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。跑道 2 原来的直行代价比 3 大,说明在这个点侧跳过去更省,于是被刷新。点 3 这一列最终定格成 2 / 3 / ∞。
- 14点 4 这里干干净净,一条障碍都没有。那三条跑道都可以从点 3 沿原跑道直行一步过来,代价原样照抄,现在跑道 1、2、3 分别是 2、3、∞。没有需要封死的格子,这一步很轻松。不过直行不一定最省,接下来还要看看在这个点侧跳一下会不会更划算。
- 15现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 4 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。
- 16最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。跑道 3 原来的直行代价比 3 大,说明在这个点侧跳过去更省,于是被刷新。点 4 这一列最终定格成 2 / 3 / 3。
- 17来到点 5,这里跑道 2 上有障碍。先把点 4 的三个代价原样搬过来,这代表青蛙沿原跑道直行一步、不侧跳。但跑道 2 这个点站不了,所以把它的代价改成无穷大,画面里用 ∞ 表示。你就理解成:想直行停在跑道 2 这个点上是不允许的,先把这条路堵死,免得后面误用它。
- 18现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 5 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。
- 19最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。通行的跑道1和跑道3直行代价是 2 和 3,都不比 3 大;跑道2被障碍封成 ∞,不参与更新。点 5 这一列最终定格成 2 / ∞ / 3。
- 20点 6 这里干干净净,一条障碍都没有。那三条跑道都可以从点 5 沿原跑道直行一步过来,代价原样照抄,现在跑道 1、2、3 分别是 2、∞、3。没有需要封死的格子,这一步很轻松。不过直行不一定最省,接下来还要看看在这个点侧跳一下会不会更划算。
- 21现在算这个点上「侧跳换道」的统一代价 x。诀窍是:先在这个点当前的三条跑道里,挑出代价最小的那条,现在是跑道 1,代价 2。从它出发,不管侧跳到另外哪条跑道,都只多花 1 次,所以 x = 2 + 1 = 3。这一个 x 就是「在点 6 侧跳一次能达到的最省代价」,待会儿拿它去更新其它跑道。
- 22最后一步,把 x = 3 拿去和每条通行跑道的直行代价比,取小的留下。跑道 2 原来的直行代价比 3 大,说明在这个点侧跳过去更省,于是被刷新。点 6 这一列最终定格成 2 / 3 / 3。
- 23整张表推满了。末点 6 三条跑道的代价是 2 / 3 / 3,取最小的那个就是答案 2。顺着倒推能还原出这条最省路线:青蛙在点 1 从跑道 2 侧跳到跑道 3,躲过点 2 跑道 2 的障碍继续直行;到点 2 又从跑道 3 侧跳到跑道 1,之后一路沿跑道 1 直行到底。全程正好 2 次侧跳,和表格算出来的 2 完全对上。
⚠️ 容易写错的地方
✗ 错：先算 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 无此问题
完整代码（Python / C++ / Java）
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]));
}
}复杂度
时间
O(n)
从左到右扫一遍每个点,每个点只在 3 条固定跑道上做常数次比较和更新,总量跟点数 n 成正比,n 到十万也秒出
空间
O(1)
按峰值算:只用一个长度 3 的滚动数组 f,每个新点只依赖上一个点的三个值,不必开二维表,所以是常数空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最少侧跳次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
状态怎么定义,转移是什么?+
设 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),但求答案本身不需要。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最少侧跳次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。