Frog Jump Memoization(Python)

Below is the problem description, followed by its recursive solution using Python. This solution is inefficient. I know using memoization, we can improve this solution. I have also gone through similar questions on StackOverflow but I couldn’t figure out the solution. I am fairly new to the memoization technique. If anyone could help me with the solution using memoization, that would be really helpful.

Problem Description: A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog’s last jump was k units, its next jump must be either k – 1, k, or k + 1 units. The frog can only jump in the forward direction.

Examples

Below is my solution using recursion(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

Here it comes up even faster memo version, it’s faster then previous version. It’s about 50% faster…

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