403. Frog Jump
https://www.jiuzhang.com/solution/frog-jump/#tag-highlight-lang-cpp
青蛙一次跳多少由上一次跳多少决定，上一次跳了k步，那么这次可以跳k-1,k,k+1这么多。从0开始，第一次只能跳一步，问能否调到最后一个石头上面。
set存储的是所有跳到当前位置的k，所以下一次能跳到的地方就是set中所有的k生成的k-1、k、k+1。
找个stones存储的是位置的索引，比如stones[1] - stones[0]就是这两个位置之间的距离。
初始点为0，且第一次只能跳1步。
class Solution { public: bool canCross(vector<int>& stones) { unordered_map<int,unordered_set<int>> dp; for(int stone : stones) dp[stone] = unordered_set<int>(); dp[0].insert(0); for(int stone : stones){ for(int k : dp[stone]){ if(k - 1 > 0 && dp.find(stone + k - 1) != dp.end()) dp[stone + k - 1].insert(k - 1); if(dp.find(stone + k) != dp.end()) dp[stone + k].insert(k); if(dp.find(stone + k + 1) != dp.end()) dp[stone + k + 1].insert(k + 1); } } return !dp[stones.back()].empty(); } };
原文：https://www.cnblogs.com/ymjyqsx/p/10940395.html