0403. 青蛙过河

• 标签：数组、动态规划
• 难度：困难

题目链接

• 0403. 青蛙过河 - 力扣

题目大意

描述：一只青蛙要过河，这条河被等分为若干个单元格，每一个单元格内可能放油一块石子（也可能没有）。青蛙只能跳到有石子的单元格内，不能跳到没有石子的单元格内。

现在给定一个严格按照升序排序的数组 $stones$，其中 $stones[i]$ 代表第 $i$ 块石子所在的单元格序号。默认第 $0$ 块石子序号为 $0$（即 $stones[0] == 0$）。

开始时，青蛙默认站在序号为 $0$ 石子上（即 $stones[0]$），并且假定它第 $1$ 步只能跳跃 $1$ 个单位（即只能从序号为 $0$ 的单元格跳到序号为 $1$ 的单元格）。

如果青蛙在上一步向前跳跃了 $k$ 个单位，则下一步只能向前跳跃 $k - 1$、$k$ 或者 $k + 1$ 个单位。

要求：判断青蛙能否成功过河（即能否在最后一步跳到最后一块石子上）。如果能，则返回 True；否则，则返回 False。

说明：

• $2 \le stones.length \le 2000$。
• $0 \le stones[i] \le 2^{31} - 1$。
• $stones[0] == 0$。
• $stones$ 按严格升序排列。

示例：

• 示例 1：

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

解题思路

思路 1：动态规划

题目中说：如果青蛙在上一步向前跳跃了 $k$ 个单位，则下一步只能向前跳跃 $k - 1$、$k$ 或者 $k + 1$ 个单位。则下一步的状态可以由 $3$ 种状态转移而来。

• 上一步所在石子到下一步所在石头的距离为 $k - 1$。
• 上一步所在石子到下一步所在石头的距离为 $k$。
• 上一步所在石子到下一步所在石头的距离为 $k + 1$。

则我们可以通过石子块数，跳跃距离来进行阶段划分和定义状态，以及推导状态转移方程。

1. 划分阶段

按照石子块数进行阶段划分。

2. 定义状态

定义状态 $dp[i][k]$ 表示为：青蛙能否以长度为 $k$ 的距离，到达第 $i$ 块石子。

3. 状态转移方程

1. 外层循环遍历每一块石子 $i$，对于每一块石子 $i$，使用内层循环遍历石子 $i$ 之前所有的石子 $j$。
2. 并计算出上一步所在石子 $j$ 到当前所在石子 $i$ 之间的距离为 $k$。
3. 如果上一步所在石子 $j$ 通过上上一步以长度为 $k - 1$、$k$ 或者 $k + 1$ 的距离到达石子 $j$，那么当前步所在石子也可以通过 $k$ 的距离到达石子 $i$。即通过检查 $dp[j][k - 1]$、$dp[j][k]$、$dp[j][k + 1]$ 中是否至少有一个为真，即可判断 $dp[i][k]$ 是否为真。
   • 即：$dp[i][k] = dp[j][k - 1] \text{ or } dp[j][k] or dp[j][k + 1] $。

4. 初始条件

刚开始青蛙站在序号为 $0$ 石子上（即 $stones[0]$），肯定能以长度为 $0$ 的距离，到达第 $0$ 块石子，即 $dp[0][0] = True$。

5. 最终结果

根据我们之前定义的状态，$dp[i][k]$ 表示为：青蛙能否以长度为 $k$ 的距离，到达第 $i$ 块石子。则如果 $dp[size - 1][k]$ 为真，则说明青蛙能成功过河（即能在最后一步跳到最后一块石子上）；否则则说明青蛙不能成功过河。

思路 1：动态规划代码

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        size = len(stones)

        stone_dict = dict()
        for i in range(size):
            stone_dict[stones[i]] = i

        dp = [[False for _ in range(size + 1)] for _ in range(size)]
        dp[0][0] = True

        for i in range(1, size):
            for j in range(i):
                k = stones[i] - stones[j]
                if k <= 0 or k > j + 1:
                    continue
                
                dp[i][k] = dp[j][k - 1] or dp[j][k] or dp[j][k + 1]

                if dp[size - 1][k]:
                    return True

        return False

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$，所以总的时间复杂度为 $O(n^2)$。
• 空间复杂度：$O(n^2)$。用到了二维数组保存状态，所以总体空间复杂度为 $O(n^2)$。

参考资料

• 【题解】【403. 青蛙过河】理解理解动态规划与dfs - 青蛙过河 - 力扣