Leetcode: 403. Frog Jump

Mistake: Misread the problem and tried to solve using a wrong DP approach.
Can we formulate the problem using graphs? Stones are vertices and two stones are connected if the frog can jump between them. The problem becomes search a path from the start position to the end using a Breadth-first search. Time and space complexity are \(O(n^2)\).

from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:
        N = len(stones)
        S = {stones[i]: i for i in range(N)}
        seen = set()
        queue = [(0, 1)]
        for i, k in queue:
            if i == N - 1:
                return True
            for d in [-1, 0, +1] if i > 0 else [0]:
                v = stones[i] + k + d
                if v not in S:
                    continue
                j = S[v]
                if (j, k + d) not in seen:
                    seen.add((j, k + d))
                    queue.append((j, k + d))
        return False