Problem statement

https://binarysearch.com/problems/Frogger/

Solution

Equal to Leetcode 0403. Frog Jump.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def solve(self, stones):
        @lru_cache(None)
        def dp(pl, st):
            if pl not in stones_set: return False
            if pl == 0 and st == 0: return True     
            if st <= 0: return False     
            return dp(pl - st, st) or dp(pl - st, st+1) or dp(pl - st, st-1)

        stones_set = set(stones)
        return any(dp(stones[-1], k) for k in range(1, len(stones)))