青蛙过河

难度: Hard

一只青蛙想要过河。假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 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 <= 2000
0 <= stones[i] <= 2³¹ - 1
stones[0] == 0
stones 按严格升序排列

Submission

运行时间: 91 ms

内存: 24.1 MB

class Solution:
    def canCross(self, A: List[int]) -> bool:
        mp = { x: i for i, x in enumerate(A)}
        n = len(A)
        @cache
        def dfs(u: int, step: int): # 当前位置, 步长
            if u == n - 1: return True
            for k in (-1, 0, 1):
                if k + step == 0: continue # 原地
                ne = A[u] + k + step
                if ne in mp and dfs(mp[ne], step + k):
                    return True
            return False

        return (1 in mp) and dfs(1, 1)

Explain

这个题解采用了记忆化搜索的方法。首先用哈希表记录每个石头的位置，然后从第二个石头开始递归搜索。递归函数 dfs(u, step) 表示当前位于第 u 个石头，上一步跳了 step 个单位。在递归过程中，如果当前已经到达最后一个石头，则返回 True；否则枚举下一步跳 step-1、step 或 step+1 个单位的情况，递归判断是否能够到达终点。为了避免重复计算，使用记忆化存储已经计算过的状态。最后判断第一步是否合法并调用 dfs 函数即可得到答案。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def canCross(self, A: List[int]) -> bool:
        mp = { x: i for i, x in enumerate(A)} # 记录每个石头的位置
        n = len(A)
        
        @cache
        def dfs(u: int, step: int): # 当前位置, 步长
            if u == n - 1: # 到达终点
                return True
            for k in (-1, 0, 1): # 枚举下一步的跳跃距离
                if k + step == 0: continue # 原地
                ne = A[u] + k + step # 下一个位置
                if ne in mp and dfs(mp[ne], step + k): # 如果下一个位置存在并且可以到达终点
                    return True
            return False

        return (1 in mp) and dfs(1, 1) # 判断第一步是否合法并开始搜索

Explore

在题解中，哈希表`mp`通过枚举数组`A`来创建，其中`A`中的每个值`x`都映射到其对应的索引`i`。这样，无论递归调用多少次，`mp[x]`始终返回石头`x`在数组`A`中的索引。这种映射关系是在哈希表初始化时一次性建立的，因此在整个递归过程中都是准确和可靠的。

根据题目设定，青蛙的起始位置是第一个石头（数组`A`的第0个索引）。青蛙的第一次跳跃必然是从第一个石头到第二个石头，因此题解中直接检查第二个石头是否存在，然后从第二个石头开始递归搜索。这是为了模仿青蛙的跳跃过程，并简化递归逻辑，因为青蛙的起始点（第一个石头）是已知且固定的。

在记忆化搜索中，使用Python的装饰器`@cache`来自动存储函数`dfs`的结果。`dfs`的每次调用都以当前的石头位置`u`和上一次的跳跃距离`step`为参数，这些参数共同构成了状态。当`dfs(u, step)`被再次调用时，`@cache`装饰器检查这个状态是否已经计算过。如果是，直接返回之前计算的结果，从而避免了重复的计算和递归调用，提高算法效率。

在青蛙过河的问题中，青蛙不能在原地踏步，即青蛙每次跳跃后必须移动到新的石头上。因此，如果计算出的下一步跳跃距离`step + k`等于0，这意味着青蛙尝试停留在当前石头上，这是不符合题目要求的。跳过`step + k`等于0的情况是为了确保每一步都向前推进，避免无效计算。这个设计符合题目规则，目前看来没有明显的潜在问题。