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:
|
|
解题思路 #
思路 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:动态规划代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,所以总的时间复杂度为 $O(n^2)$。
- 空间复杂度:$O(n^2)$。用到了二维数组保存状态,所以总体空间复杂度为 $O(n^2)$。