LeetCode 题解工作台
青蛙过河
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。 给你石子的位置列表 stones （用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站…
2
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们用哈希表 记录每个石子的下标，接下来设计一个函数 $dfs(i, k)$，表示青蛙从第 个石子跳跃且上一次跳跃距离为 ，如果青蛙能够到达终点，那么函数返回 `true`，否则返回 `false`。 函数 $dfs(i, k)$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：
输入：stones = [0,1,3,5,6,8,12,17] 输出：true 解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
示例 2：
输入：stones = [0,1,2,3,4,8,9,11] 输出：false 解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
提示：
2 <= stones.length <= 20000 <= stones[i] <= 231 - 1stones[0] == 0stones按严格升序排列
解题思路
方法一：哈希表 + 记忆化搜索
我们用哈希表 记录每个石子的下标，接下来设计一个函数 ，表示青蛙从第 个石子跳跃且上一次跳跃距离为 ，如果青蛙能够到达终点，那么函数返回 true，否则返回 false。
函数 的计算过程如下：
如果 是最后一个石子的下标，那么青蛙已经到达终点，返回 true；
否则，我们需要枚举青蛙接下来的跳跃距离 ，其中 。如果 是正数，并且哈希表 中存在位置 ，那么青蛙在第 个石子上可以选择跳跃 个单位，如果 返回 true，那么青蛙可以从第 个石子成功跳跃到终点，我们就可以返回 true。
枚举结束，说明青蛙在第 个石子上无法选择合适的跳跃距离跳到终点，我们就返回 false。
为了防止函数 中出现重复计算，我们可以使用记忆化搜索，将 的结果记录在一个数组 中，每当函数 返回结果，我们就将 进行赋值，并在下次遇到 时直接返回 。
时间复杂度 ，空间复杂度 。其中 是石子的数量。
class Solution:
def canCross(self, stones: List[int]) -> bool:
@cache
def dfs(i, k):
if i == n - 1:
return True
for j in range(k - 1, k + 2):
if j > 0 and stones[i] + j in pos and dfs(pos[stones[i] + j], j):
return True
return False
n = len(stones)
pos = {s: i for i, s in enumerate(stones)}
return dfs(0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity varies with the number of stones and reachable jumps per stone; in the worst case, it can approach O(n^2). Space complexity is O(n*m) where m is the average number of jumps stored per stone. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can you model this problem as a state transition dynamic programming scenario?
- question_mark
What data structure can efficiently track reachable positions with jump constraints?
- question_mark
How do you prune moves that cannot possibly lead to the last stone?
常见陷阱
外企场景- error
Assuming constant jump sizes instead of k-1, k, k+1 transitions.
- error
Neglecting to check if a jump lands on a valid stone before updating states.
- error
Failing to initialize the first jump correctly at 1 unit, causing early DP failure.
进阶变体
外企场景- arrow_right_alt
Determine the minimum number of jumps needed to reach the last stone using the same k-1, k, k+1 rule.
- arrow_right_alt
Return all possible sequences of jumps that allow the frog to reach the last stone.
- arrow_right_alt
Allow backward jumps under specific constraints and adapt the DP accordingly.