403. Frog Jump

O(n²) time O(n²) space
因为stones[0]是0且初始步长是0所以步长最多为n也就是最多n种，所以对于每个stones[i]步长最多n种，复杂度O(n²)

class Solution {
public:
    bool canCross(vector<int>& stones) {
        for (int i = 0, limit = 0; i < stones.size(); ++i) { // 可有可无，只是一个优化，假设前面每一跳都比前面一跳加1，那么到第i跳之后应该到 i * (i  + 1) / 2，假如stones[i]比这个要远，则意味着永远到不了stones[i]
            limit += i;
            if (stones[i] > limit) return false;
        }
        return canCross(stones, 0, 0);
    }

    bool canCross(const vector<int> &stones, int b, int k) { // 上一步步长为k达到的stones[b]，从b + 1开始遍历看[k - 1, k + 1]步长之内能到哪些stones
        int n = stones.size();
        if (b == n - 1) return true;
        auto key = (k << 11) | b; // 如果是全部integer则要用long key = (k << 32) | b;
        if (m.count(key)) return m[key];
        for (int i = b + 1; i < n; ++i) { // 这个循环实际上只需要遍历最多三个stones
            int jump = stones[i] - stones[b];
            if (jump < k - 1) continue;
            if (jump > k + 1) break;
            if (canCross(stones, i, jump)) return m[key] = true;
        }
        return m[key] = false;
    }

    unordered_map<int, bool> m; // 每个石头的下标+尝试到达stones[i]所需要的步长 和 用这个步长是否能到达stones[i]
};

class Solution {
public:
    bool canCross(vector<int>& stones) {
        n = stones.size();
        for (int i = 0; i < n; ++i) {
            dict[stones[i]] = i;
        }
        return canCross(stones, 0, 1);
    }

    bool canCross(const vector<int> &stones, int b, int k) {
        if (k <= 0) return false;
        if (b == n - 1) return true;
        auto key = (k << 11) | b;
        if (m.count(key)) return m[key];
        int next = stones[b] + k;
        if (dict.count(next) == 0) return false;
        for (int d = -1; d <= 1; ++d) {
            if (canCross(stones, dict[next], k + d)) return m[key] = true;
        }
        return m[key] = false;
    }

    int n;
    unordered_map<int, int> m, dict;
};

O(n²) time O(n²) space

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> m; // 每个石头的位置stones[i]和到stones[i]有可能的步长
        for (int s : stones) {
            m[s] = {}; // 这一步必须要有，否则无法判断是否存在指定位置的石头
        }
        m[stones[0]].insert(0);
        for (int s : stones) {
            for (int k : m[s]) { // 每个石头最多只可能继承n种步长（否则就到最后一个了）所以内循环复杂度上限是O(n)
                for (int d = -1; d <= 1; ++d) {
                    int t = s + k + d;
                    if (t == stones.back()) return true;
                    if (k + d > 0 && m.count(t)) {
                        m[t].insert(k + d);
                    }
                }
            }
        }
        return false;
    }
};