一只青蛙想要过河。 假定河流被等分为若干个单元格，并给出石子的所在单元格的位置列表
stones（表示用单元格序号 升序 ）。 青蛙可以跳上石子，但是不可以跳入水中。请判定青蛙能否成功过河（即能否跳至最后一块石子上）。
开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃
1 个单位（即只能从单元格 1 跳至单元格 2 ）。如果青蛙上一步跳跃了
k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：
示例 2：
说明：
2 <= stones.length <= 2000
0 <= stones[i] <= 231 1
stones[0] == 0
stones按严格升序排列
解法一：哈希表 + 记忆化搜索 （推荐）
给定一组递增排列的石子位置
stones，青蛙一开始站在 stones[0] = 0，第一跳必须跳 1 个单位；如果上一跳距离是 k，下一跳只能跳 k - 1、k 或 k + 1 个单位，问青蛙能不能跳到最后一块石子。这道题看起来像 DFS 路径搜索：青蛙站在某块石子上，尝试往后跳。
但区别在于，只知道当前石子还不够，还必须知道上一跳跳了多远。因为下一跳的可选距离依赖上一跳：
next_jump ∈ {k - 1, k, k + 1}且搜索树很容易产生重复状态。比如青蛙可能通过不同路径来到同一块石子，并且上一跳距离也一样。
一旦
(i, k) 相同，后续能不能到终点的答案就完全一样，不应该重复计算。所以我们用记忆化搜索缓存
dfs(i, k) ，表示青蛙当前站在第 i 块石子上，并且上一跳距离是 k，从这个状态出发能不能到达最后一块石子。如果某个状态已经算过，下次直接返回缓存结果。
如果下一跳距离是
step，那么青蛙要跳到的位置是：stones[i] + step问题是：这个位置上有没有石子？
如果每次都在线性数组里查找这个位置，搜索会很慢。所以我们提前建一个哈希表：
pos = {stone_position: index}这样就可以在
O(1) 时间判断某个位置是否存在石子，并快速拿到对应下标。以
stones = [0, 1, 3, 5, 6, 8, 12, 17]为例，青蛙从 0 出发，第一跳只能跳到 1。到了位置 1 后，上一跳是 1步，所以下一跳可以尝试 1 或 2步；如果跳 2步，就能到位置 3。继续往后，一条成功路径是
0 -> 1 -> 3 -> 5 -> 8 -> 12 -> 17，对应跳距是 1, 2, 2, 3, 4, 5。当状态到达最后一块石子时，递归返回 True。如果另一条分支走到
dfs(4,1)，也就是青蛙在位置 6、上一跳距离为 1，只能跳到位置8，但后续无法到达终点，那么这个状态会被缓存为 False；之后再次遇到同样的 (4,1)，就可以直接返回，避免重复搜索。复杂度分析
- 时间复杂度是
O(n^2)。
状态由
(i, k) 决定。i 最多有 n 种取值；k 的有效范围也不会无限增长，最多可以按 O(n) 估计。因此状态总数是 O(n^2)。每个状态最多尝试三种下一跳，所以总时间复杂度是 O(n^2)。- 空间复杂度是
O(n^2)
主要来自 缓存状态。递归栈最深为
O(n)，但被缓存空间主导。解法二：Bottom-up DP
记忆化搜索是从当前状态往后试；Bottom-up DP 则反过来，从已经能到达的状态出发，推导后续状态。
定义：
dp[i][k] = True ，表示青蛙可以到达第 i 块石子，并且到达它时，上一跳距离是 k。初始状态是
dp[0][0] = True，意思是青蛙一开始站在第 0 块石子上，上一跳距离可以看作 0。接下来考虑第
i 块石子能不能从之前某块石子 j 跳过来。假设
k = stones[i] - stones[j] ，表示从 j 跳到 i 的距离是 k。那么在
j 位置时，上一跳距离必须是下面三种之一：k - 1, k, k + 1因为如果上一跳是
k - 1、k 或 k + 1，下一跳就有可能跳出距离 k。所以状态转移是：
dp[i][k] = dp[j][k - 1] or dp[j][k] or dp[j][k + 1]只要其中一个为
True，说明可以从 j 跳到 i，并且到达 i 时上一跳距离就是 k。复杂度分析
- 时间复杂度是
O(n^2)
我们枚举当前石子
i 和上一块石子 j，总共有 O(n^2) 对。每次状态转移只检查三个布尔值，所以是常数时间。- 空间复杂度是
O(n^2)
因为需要维护
dp[i][k] 这张二维表。总结
这道题的核心是状态定义。青蛙下一跳能跳多远，不只取决于当前在哪块石子上，还取决于上一跳跳了多远。所以状态必须是
(i, k)，其中 i 是当前石子下标，k 是上一跳距离。两种做法时间复杂度都是
O(n^2)，空间复杂度也是 O(n^2)。 - 记忆化搜索是 Top-down。
dfs(i, k)表示 当前在 i，上一次跳了 k，接下来能不能到终点？- 它从起点开始，只搜索真正可达的状态，遇到重复状态就缓存。
- Bottom-up DP 是反向填表。
dp[i][k]表示青蛙能不能到达 i，并且到达 i 时上一跳刚好是 k？- 它枚举石子对
(j, i)，判断是否能从j转移到i。
这两种写法本质上是同一个 DP，只是计算方向不同。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-403-青蛙过河
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 398] 随机数索引
下一篇
[Leetcode 473] 火柴拼正方形