Hard 622. Frog Jump

way 1: DP, 坐标+状态 型动态规划.
先找到变化的维度或数据, i.e. 状态 = 步长 j, 0 < j < i + 1; n 个石头, 每次步长加一, 最大跳 n 单元.
再简化可以推导出的维度.

数据结构: v_idx = {v:i for i, v in enumerate(A)} 反向索引, {val : index}

子问题: f[i][j], 跳到 stones[i] 需要 j 步.
方程: f[i][j] = f[k][j] or f[k][j + 1] or f[k][j - 1]. k = val_idx[A[i] - j], 如果 A[k] 存在.
init: f[0][0] = f[1][1] = True
计算顺序:
for i in range(2, n):
  for j in range(i + 1):
     f[i][j] = ..;

way 2: DP + hashmap set

<code 1>
class Solution:
    def canCross(self, stones):
        # init
        A = stones
        n = len(A)
        if n < 2:
            return True
        if A[1] != 1:
            return False
        v_idx = {v:i for i, v in enumerate(A)}
        f = [[False] * (n + 2) for _ in range(n)]
        f[0][0] = f[1][1] = True

        for i in range(2, n):
            for j in range(i):
                kv = A[i] - j
                if kv not in v_idx:
                    continue
                k = v_idx[kv]
                if f[k][j] or f[k][j + 1] or f[k][j - 1]:
                    f[i][j] = True

        ans = any(f[n - 1])
        return ans

stones = [0,1,3,5,6,8,12,17]
# True
;