算法1

(BFS) $O(n^2)$

C++ 代码

typedef pair<int, int> pii;

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_set<int> sts(stones.begin(), stones.end());
        auto hash = [&](const pii& p){ return (size_t)(p.first * 31 + p.second); };
        unordered_set<pii, decltype(hash)> used(10, hash);
        int dest = stones.back();
        queue<pii> q;
        q.push({stones[0], 0});
        while(q.size()) {
            auto node = q.front(); q.pop();
            if(used.count(node)) continue;
            used.insert(node);
            int st = node.first, k = node.second;
            if(st == dest) return true;

            for(int i = -1; i <= 1; i++) {
                int tk = k + i, ne = st + k + i;
                if(tk <= 0 || sts.find(ne) == sts.end()) continue;
                q.push({ne, tk});
            }
        }
        return false;
    }
};

// 如果用{stone, k}表示状态
// 那么最坏时间复杂度是多少呢？
// o(n**2) = 4e6


// 可以不用k来表示，因为两点之间的距离确定了K
// 所以可以用当前点x，和上一个点pre来表示

typedef pair<int, int> pii;

class Solution {
private:
    bool used[2010][2010];
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, int> map;
        for(int i = 0; i < stones.size(); i++) 
            map[stones[i]] = i;
        int dest = stones.back();
        queue<pii> q;
        q.push({0, 0});
        memset(used, false, sizeof used);
        while(q.size()) {
            auto p = q.front(); q.pop();
            auto x = p.first, pre = p.second;
            if(used[x][pre]) continue;
            used[x][pre] = true;
            int cur = stones[x];
            int k = cur - stones[pre];

            for(int i = -1; i <= 1; i++) {
                int tk = k + i, ne = cur + k + i;
                if(tk <= 0 || map.find(ne) == map.end()) continue;
                if(ne == dest) return true;
                q.push({map[ne], x});
            }
        }
        return false;
    }
};

算法2

(DP) $O(n^2)$

C++ 代码

class Solution {
private:
    bool f[2010][2010];
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, int> map;
        for(int i = 0; i < stones.size(); i++) 
            map[stones[i]] = i;
        f[0][0] = true;
        int n = stones.size();
        for(int j = 0; j < n; j++)
            for(int i = 0; i <= j; i++) {
                int pre = i, x = j;
                if(!f[pre][x]) continue;
                int cur = stones[x], k = cur - stones[pre];
                for(int o = -1; o <= 1; o++) {
                    int tk = k + o, ne = cur + tk;
                    if(tk <= 0 || map.find(ne) == map.end()) continue;
                    auto tid = map[ne];
                    if(tid == n - 1) return true;
                    f[x][map[ne]] = true;
                }
            }
        return false;
    }
};

// 如果用{stone, k}表示状态
// 那么最坏时间复杂度是多少呢？
// o(n**2) = 4e6

// 可以不用k来表示，因为两点之间的距离确定了K
// 所以可以用当前点x，和上一个点pre来表示

// 然后可以用DP了。。。
// f(x,y): 从x走到y的路线集合
// 属性：能否从x走到y
// x < y, f(x,y) = i=[0..x] f(i, x) && stones[x] - stones[i] 符合条件
// 时间复杂度：1/2 (1 * 1 + ... + n * n) = o(n ** 3) ???

// 换一种方式:
// x < y, f(x,y) -> f(y, appropriate id)
// f(0, 0) = true
// 时间复杂度：o(1/2 * (n ** 2))
// 太多冗余，比搜索要慢。。。