记忆化搜索

参考代码：

class Solution {
public:

    /*
        状态表示：f[i][j]表示跳到i号位置，且从i可以往后跳的长度为j！ 属性：方案是否合法！
        状态计算：
            考虑能够从f[hash[stones[i] - k]][k]转移过来即可！
            注：k可取值为j - 1, j, j + 1
            hash[stones[i] - k]表示上一步石头的编号！

        快速查找下标位置是否有石头，可以利用哈希表快速查找！

        记忆化搜索：可减少一些对答案无关的状态计算！优化一点常数！目前直接使用DP两层循环是超时的！
    */

    unordered_map<int, int> hash;
    // -1：未计算 0：不合法 1：合法
    int f[2010][2010];
    vector<int> stones;

    // 第i号石头能否往后跳j步
    bool dp(int i, int j){
        // 算过则直接返回
        if(f[i][j] != -1) return f[i][j];
        // 置0
        f[i][j] = 0;
        // 枚举上一次跳的三种情况：j - 1, j, j + 1
        for(int k = max(1, j - 1); k <= j + 1; k ++){
            // 确保该位置有石头
            if(hash.count(stones[i] - k)){
                // 若该位置跳k步合法，hash[stones[i] - k] ---> 该位置石头的编号（从0开始）
                if(dp(hash[stones[i] - k], k)){
                    f[i][j] = 1;
                    break;
                }
            }
        }
        return f[i][j];
    }

    bool canCross(vector<int>& _stones) {
        stones = _stones;
        int n = stones.size();
        for(int i = 0; i < n; i ++) hash[stones[i]] = i;

        memset(f, -1, sizeof f);
        // 0号位第一块石头跳一步状态合法！
        f[0][1] = 1;
        for(int i = 0; i < n; i ++)
            // 枚举能否最后一块石头能否往后跳i步！
            // 有一个合法即可以跳到最后一块石头！
            if(dp(n - 1, i)) return true;
        return false;
    }
};

动态规划

写法参考 @RyanL ！

参考代码：

class Solution {
public:

    /*
        状态表示：f[i][j]表示跳到i号石头，且上一步往后跳的长度为j 属性：方案是否合法！
        状态计算：
            枚举每一个上一步跳到的位置j，跳到上一步位置的距离可以为k - 1, k和k + 1
            所以f[i][k] = f[j][k-1] || f[j][k] || f[j][k+1]
            并且跳跃距离k = stones[i] - stones[j]
            必须满足k <= j + 1，因为第j个位置最多只能跳跃j+1个距离
    */

    int f[2010][2010];

    bool canCross(vector<int>& stones) {
        int n = stones.size();
        // 上一步不跳，处于0号石头合法
        f[0][0] = 1;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < i; j ++){ // 枚举上一个石子编号
                // 上一步跳的步数
                int k = stones[i] - stones[j];
                // 第j个位置最多跳j + 1长度！
                if(k <= j + 1) f[i][k] = f[j][k - 1] || f[j][k] || f[j][k + 1];
            }
        // 准确来说：至少跳一步
        for(int i = 1; i < n; i ++) if(f[n - 1][i]) return true;
        return false;
    }
};