0403. 青蛙过河

0403. 青蛙过河 #

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

题目大意 #

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

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

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

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

要求:判断青蛙能否成功过河(即能否在最后一步跳到最后一块石子上)。如果能,则返回 True;否则,则返回 False

说明

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

示例

1
2
3
输入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 - 1k 或者 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 - 1k 或者 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:动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)$。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者