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] 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 - 青蛙过河 - 力扣