403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be eitherk - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

Example 1:

[0,1,3,5,6,8,12,17]There are a total of 8 stones.The first stone at the 0th unit, second stone at the 1st unit,third stone at the 3rd unit, and so on...The last stone at the 17th unit.Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11]Return false. There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
Subscribe to see which companies asked this question.
给出一系列石头的位置，青蛙要从第一块跳到最后一块，第一次跳的距离只能是1，设某一次跳的值k，则下一次跳的距离只能是k-1, k, k+1，而且只能往前跳。问能不能跳到最后一块。原本是用dfs做的，但超时了。后来改为用dp方法。对每一个位置，用集合set记录好哪些位置能跳到当前位置，事实上记录跳的距离就行了。然后对当前位置对应的集合的所有k值，看它后面的位置是否能跳到，在能跳到的位置对应的集合记录好跳的距离。这样只要最后的位置的集合不为空，就能到达。
代码：
class Solution{public:	bool canCross(vector<int>& stones)	{		if(stones[1] != 1) return false;		int n = stones.size();		vector<unordered_set<int> > a(n);		a[1].insert(1);		for(int i = 1; i < n; ++i)		{			for(int j = i+1; j < n; ++j)			{				int unit = stones[j] - stones[i];				for(auto it = a[i].begin(); it != a[i].end(); ++it)				{					int k = *it;					if(unit > k+1) continue;					if(unit < k-1) break;					a[j].insert(unit);				}			}			if(!a[n-1].empty()) return true;		}		return false;	}};