from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:
        N = len(stones)
        d = {}
        if stones[1] != 1: # if we cannot jump at initial place, it definitely False
            return False
        # build value-index mapping
        for i, stone in enumerate(stones):
            d[stone] = i
        # dp is the number of jumps to location i
        # for example, we can only jump to pos 1 with 1 units
        # if we can jump to pos X for {a, b, c} units, it means that we can jump to X for a, b, c units
        # it also means that from pos X, we can jump for <a-1, a, a+1, b-1, b, b+1, c-1, c, c+1> units. 
        dp = [{0}, {1}]
        for i in range(2, N):
            dp.append(set())
        for i in range(1, N):
            s = stones[i]
            for k in dp[i]:
                # do jump
                # if k-1 is ok for position stones[i], jump and add to dp
                if s + k - 1 in d and k - 1 != 0:
                    dp[d[s + k - 1]].add(k - 1)
                # if k is ok for position stones[i], jump and add to dp
                if s + k in d and k != 0:
                    dp[d[s + k]].add(k)
                # if k+1 is ok for position stones[i], jump and add to dp
                if s + k + 1 in d and k + 1 != 0:
                    dp[d[s + k + 1]].add(k + 1)
        return len(dp[-1]) != 0