青蛙跳跃记忆化(Python)

Question

下面是问题描述，然后是使用Python的递归解决方案。这种解决方案效率低下。我知道使用记忆，我们可以改进这个解决方案。我在StackOverflow上也遇到过类似的问题，但我无法找到解决方案。我对记忆技术相当陌生。如果有人能帮助我解决使用记忆的问题，那将非常有帮助。

问题描述：一只青蛙正在渡河。河流被分成若干单元，在每个单元处，可能存在也可能不存在一块石头。青蛙可以在石头上跳，但决不能跳进水里。

给出一个按升序排列的石头位置列表(单位(，确定青蛙是否可以通过落在最后一块石头上渡河。最初，青蛙在第一块石头上，并假设第一次跳跃必须是1个单位。

如果青蛙的最后一跳是k个单位，那么它的下一跳必须是k-1、k或k+1个单位。青蛙只能向前跳。

示例

下面是我使用递归(Python(的解决方案。

class Solution:
def canCross(self, stones: List[int]) -> bool:
return self.helper(stones[0],stones,1)

def helper(self,curr,stones,k):
if curr+k == stones[-1]:
return True

if not curr+k in stones or k<=0: 
return False
else:
curr = curr+k 
return self.helper(curr,stones,k-1)  or self.helper(curr,stones,k) or self.helper(curr,stones,k+1)

Answer 1

这里出现了更快的memo版本，它比以前的版本更快。它大约快50%。。。

class Solution:
"""
"""
def canCross(self, stones: List[int]) -> bool:
self.target = stones[-1]
stones = set(stones)
return self.dfs(stones, 0, 0, {})
def dfs(self, stones, cur, k, memo):
if cur == self.target:
return True
if (cur, k) in memo:
return memo[(cur, k)]
for nxt in [k-1, k, k+1]:
if nxt > 0 and cur + nxt in stones:
if self.dfs(stones, cur+nxt, nxt, memo):
memo[(cur, k)] = True
return True
memo[(cur, k)] = False
return False

Answer 2

@Krishna，

请尝试这个memo版本，看看速度是否会加快。

def canCross(self, stones: List[int]) -> bool:
if stones[1] != 1:
return False
d = {x: set() for x in stones}
d[1].add(1)
for x in stones[:-1]:
for j in d[x]:
for k in range(j-1, j+2):
if k > 0 and x+k in d:
d[x+k].add(k)
return bool(d[stones[-1]])

Answer 3

functools装饰器，用于类中方法的存储：

from functools import cached_property
class Solution:
def canCross(self, stones: List[int]) -> bool:
return self.helper(stones[0],stones,1)

@cached_property
def helper(self,curr,stones,k):
if curr+k == stones[-1]:
return True

if not curr+k in stones or k<=0: 
return False
else:
curr = curr+k 
return self.helper(curr,stones,k-1)  or self.helper(curr,stones,k) or self.helper(curr,stones,k+1)