Problem statement

https://leetcode.com/problems/frog-jump/

Solution

Classical DP problem, let dp(place, step) be equal to True, if it is possible to reach place such that last step was made is step. We need to look to 3 positions: dp(place - step, step), dp(place - step, step + 1), dp(place - step, step - 1). We can use lru_cache in python, which is quite useful. Or we can use standard n x n table.

Complexity

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

Code

class Solution:
    def canCross(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)))