两种做法 即便看了官方题解 还是想了好久才通 我是fw 太菜了 撸不动代码了
下面代码块和latex混用了 看的懂就好
“位置$i$”等同于stones[i] 意会意会

首先
有一个特性需要明确 两个做法都有用到

位置$0$最大跳跃距离$k_0=1$
位置$1$最大跳跃距离$k_1=k_0+1=2$
位置$2$最大跳跃距离$k_2=k_1+1=3$
·····
位置$i$最大跳跃距离$k_i=i+1$

因此若存在$j < i$且stones[i] - stones[j] > j + 1 则stones[i]必定不可到达
（说白了 两个石头的距离不能超过“靠前的那个石头”的最大跳跃距离 否则肯定跳不到后一个石头）

考虑某个位置$i$能否“被位置$j$以某个距离$k$跳到” 也只需要考虑到$k <= j + 1$

DP

状态表示 $f(i,k)$ 表示“当前位置为stones[i]且上一步跳跃了$k$的距离才到达当前位置”
属性值 $true$或$false$ 表示位置$i$在距离$k$的前提下是否可到达

状态计算
记上一步在位置$j$
则当stones[j] + k == stones[i]且$k <= j + 1$时 有希望从位置$i$跳跃到位置$j$

什么时候能确定可以到达呢 即$f(i,k)=true$
若位置$j$ 跳了$k$ 到达位置$i$
则位置$j$的上一步有可能是“$k - 1$”、“$k$”、“$k + 1$” 然后再对应以“+1”、“+0”、“-1”的方式 跳了$k$到位置$i$
所以位置$i$能否到达 关键在于它的前一步“位置$j$”是否可达
因此 $f(i,k)$能否为$true$ 取决于 $f(j,k-1)$、$f(j,k)$、$f(j,k+1)$ 中是否有一个为$true$

状态计算式为 $f(i,k) = f(j,k-1) \cup f(j,k) \cup f(j,k+1)$

注意位置$j$是不确定的 对应的距离$k$也是不确定的
所以在推导时 需要枚举之前所有的石子位置 找出所有可能的情况

这里的第二层循环是枚举上一步的位置$j$ 再通过stones[i] - stones[j]得到应该跳跃的距离$k$

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        for (int i = 1; i < n; i++) {
            if (stones[i] - stones[i - 1] > i) return false;  // 提前排除一定不可达的情况
        }

        boolean[][] f = new boolean[n][n];
        f[0][0] = true;  // 初始时青蛙在位置0且上一步跳跃的距离为0 标记为可达
        for (int i = 1; i < n; i++) {  // 当前位置
            for (int j = 0; j < i; j++) {  // 上一步位置
                int k = stones[i] - stones[j];  // 两者之间的距离
                if (k > j + 1) continue;  // 若距离大于“最大可跳跃的距离” 则不能由这个j直接跳到i
                f[i][k] = f[j][k - 1] || f[j][k] || f[j][k + 1];  // 如果可以直接跳 能否到达i取决于有没有合适的j
            }
        }
        for (int i = n - 1; i >= 0; i--) {  // 循环查看最后一个石子是否可达
            if (f[n - 1][i]) return true;
        }
        return false;
    }
}

记忆化搜索

深搜的改良

加一个布尔数组（含义类似上面DP的状态数组）
vis[i][k] 标记“当前位置为stones[i]且上一步跳跃了$k$的距离才到达当前位置”的状态是否已被搜过

在搜某个(i, k)时 先判断当前状态是否已经被搜过 搜过了就证明当前状态到不了终点 否则上次搜到时就直接返回true了

上代码

class Solution {
    HashMap<Integer, Integer> map;  // 反转一下数组对应关系 {stones[index]:index} 方便判断某个位置是否有石头 以及这个位置在stones[]里的索引位置
    int[] s;  // stones[]
    int n;  // 数组总长度
    boolean[][] vis;  // 记忆化搜素

    private boolean dfs(int idx, int k) {
        if (idx == n - 1) return true;  // 找到了
        if (idx >= n) return false;  // 越界了
        if (vis[idx][k]) return false;  // 已经找过了
        for (int dk = -1; dk <= 1; dk++) {  // 新的跳跃距离有三种选择 在上次跳跃的基础上±1或+0
            int kk = k + dk;  // 新的跳跃距离
            int next = s[idx] + kk;  // 下一个位置的实际坐标
            if (kk <= 0 || !map.containsKey(next)) continue;  // 不能后退 且 next必须有石头（即next在stones[]中）
            if (dfs(map.get(next), kk)) return true;  // 注意dfs的不是next 而是next在stones[]中的索引位置
            // 如果找到就会逐层返回true 直接结束深搜
        }
        vis[idx][k] = true;  // 这条路不成功 把当前状态标记为“已搜过”
        return false;  // 此路不通
    }

    public boolean canCross(int[] stones) {
        map = new HashMap<>();
        s = stones;
        n = stones.length;
        vis = new boolean[n][n];

        map.put(stones[0], 0);
        for (int i = 1; i < n; i++) {
            if (stones[i] - stones[i - 1] > i) return false; // 提前排除一定不可达的情况
            map.put(stones[i], i);  // 反转一下数组对应关系 {stones[index]:index}
        }
        return dfs(0, 0);
    }
}