Skip to main content

403.青蛙过河

标签: dynamic-programming, depth-first-search

难度: Hard

通过率: 46.3%

原题链接: https://leetcode.com/problems/frog-jump/description/

题目描述

一只青蛙正在过河。这个河被分成了若干个单元,每个单元可能有也可能没有石头。青蛙可以停在石头上,但不能跳入水中。给定石头的位置列表(按升序排列),确定青蛙是否能通过所有石头到达最后一块石头。青蛙一开始在第一块石头上,并假设第一次跳跃必须是1个单位。如果青蛙的最后一次跳跃是k个单位,则下次跳跃必须是k-1、k或k+1个单位。青蛙只能向前跳。

解题思路

为了判断青蛙是否可以跳到最后一个石头,我们可以使用动态规划结合深度优先搜索的方法。我们用一个字典来记录青蛙在每个石头上能以哪些步长(k)到达。初始情况下,只有第一块石头上有步长为0的可能。然后对每一块石头,计算以每种可能的步长k到达该石头的情况下,青蛙下一步可能的的跳跃步长,为k-1, k和k+1。若这三种步长能到达的石头存在,我们就在对应的石头上添加新的步长可能性。循环遍历迭代这一过程直到处理所有石头。如果最后一块石头有任何可能的步长到达,则表示青蛙可以到达,否则不可以。

代码实现

def canCross(stones):
# 记录那些石头可以以哪些步长(k)到达
dp = {stone: set() for stone in stones}
dp[stones[0]].add(0)

for stone in stones:
for k in dp[stone]:
# 尝试k-1, k, k+1步长的跳跃
for step in [k - 1, k, k + 1]:
if step > 0 and (stone + step) in dp:
dp[stone + step].add(step)

# 查看最后一个石头是否存在能以某个步长到达
return bool(dp[stones[-1]])

复杂度分析

时间复杂度为 O(n2)O(n^2),其中 nn 是石头的数量,因为每个石头可以检查的步长可能性最多有 nn 个。

空间复杂度为 O(n2)O(n^2),字典用来存储每块石头的步长可能性。