蛙跳记忆(Python)

Question

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

问题描述：一只青蛙正在过河。这条河被分成一些单元，在每个单元中，可能有也可能没有石头。青蛙可以跳到石头上，但不能跳进水里。

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

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

Examples

下面是我使用递归的解决方案(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 版本，看看速度是否加快。


     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 2

这里出现了更快的 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 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)

蛙跳记忆(Python)

Frog Jump Memoization(Python)

python

memoization