題意
給定一個(gè)石頭的序列，青蛙從0開始跳，第一次只能跳一步，不能落入水中。
現(xiàn)在，假如我從上一個(gè)石頭跳到這個(gè)石頭是k步，那么，我們下一次只能跳k - 1或k或k + 1步，問：青蛙最后能否調(diào)到最后一個(gè)石頭上。
思路
算法1
爆搜，本來以為會(huì)T，但是實(shí)際上中間會(huì)有很多情況會(huì)落入水中，所以bfs能過。
算法2
dp，我們可以這樣考慮：我們當(dāng)前在位置i，是從位置j經(jīng)過k步到達(dá)位置i的。那么我們下一次能夠達(dá)到stonesi+k或stonesi+k?1或stonesi+k+1。
于是，我們的狀態(tài)表示為：d[i]，從i之前的某一位置j經(jīng)過k步跳過來的，那么，很明顯我們的d[i]有很多種情況，我們可以再加一維j表示從j經(jīng)過d[i,j]步跳過來的，也可以用一個(gè)set來存我們經(jīng)過多少步到i的。
即，我們定義我們的d[i]為unordered_map<int, set<int>> pos，key為stones[i]，value為跳到這個(gè)位置的所有可能步數(shù)集合。
那么，我們接下來需要做的就是：假設(shè)我們當(dāng)前在位置i，我們?nèi)〕鰌os[stones[i]]對(duì)應(yīng)的集合tk。對(duì)于tk內(nèi)的每一個(gè)步數(shù)k，那么我們下一次就可以走到的位置newpos為stones[i] + k或stones[i] + k - 1或stones[i] + k + 1。然后判斷newpos是否為一個(gè)石頭，如果是，那么我們就將可行的解加入pos即可。
最后，只需要判斷pos[stones[n - 1]].size()>0即可（即是否存在到終點(diǎn)的可行步數(shù)）
代碼
//algorithm 1#define PII pair<int, int>#define mp make_pairclass Solution {public: bool canCross(vector<int>& stones) { set<PII> vis; set<int> has; for (auto x : stones) has.insert(x); int ll = stones[stones.size() - 1]; queue<PII> q; q.push(mp(1, 1)); while (!q.empty()) { PII t = q.front(); q.pop(); if (t.first == ll) return true; if (vis.find(t) != vis.end()) continue; else vis.insert(t); int x = t.first, k = t.second; if (has.find(x) != has.end()) { if (x + k <= ll && has.find(x + k) != has.end()) q.push(mp(x + k, k)); if (x + k - 1 <= ll && has.find(x + k - 1) != has.end()) q.push(mp(x + k - 1, k - 1)); if (x + k + 1 <= ll && has.find(x + k + 1) != has.end()) q.push(mp(x + k + 1, k + 1)); } } return false; }};//algorithm 2class Solution {public: bool canCross(vector<int>& stones) { unordered_map<int, set<int>> pos; set<int> tmp; for (auto x : stones) pos[x] = tmp; for (int i = 0; i < stones.size(); i++) { set<int> sk = pos[stones[i]]; for (auto k : sk) { for (int step = k - 1; step <= k + 1; step++) { if (step > 0 && pos[stones[i] + step] != NULL) pos[stones[i] + step].insert(stones[i] + step); } } } return pos[stones.size() - 1].size() > 0; }};
