0403. 青蛙过河
大约 4 分钟
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
。
说明:
- 。
- 。
- 。
- 按严格升序排列。
示例:
- 示例 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. 状态转移方程
- 外层循环遍历每一块石子
i
,对于每一块石子i
,使用内层循环遍历石子i
之前所有的石子j
。 - 并计算出上一步所在石子
j
到当前所在石子i
之间的距离为k
。 - 如果上一步所在石子
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:复杂度分析
- 时间复杂度:。两重循环遍历的时间复杂度是 ,所以总的时间复杂度为 。
- 空间复杂度:。用到了二维数组保存状态,所以总体空间复杂度为 。