C++ DP solution

• ``````class Solution {
public:
bool canCross(vector<int>& stones) {
if(stones.size() <= 1)
return true;
if(stones.size() == 2)
return stones.back() == stones[0] + 1;
if(stones[1] != stones[0] + 1)
return false;
map<int, set<int> > result;
set<int> first;
first.insert(stones[0]);
result[0] = first;
set<int> second;
second.insert(stones[1]);
result[1] = second;
int maxReach = 3;
int maxJumpUnit = 2;
bool canReach = false;
for(vector<int>::size_type n = 2; n < stones.size(); ++n){
if(stones[n] > maxReach)
return false;
for(map<int, set<int> >::size_type i = 1; i <= maxJumpUnit; ++i){
int prevStonePos = stones[n] - i;
map<int, set<int> >::iterator prevStoneIndex = result.find(i-1);
if((prevStoneIndex != result.end() && prevStoneIndex->second.find(prevStonePos) != prevStoneIndex->second.end())
||((prevStoneIndex = result.find(i)) != result.end() && prevStoneIndex->second.find(prevStonePos) != prevStoneIndex->second.end())
||((prevStoneIndex = result.find(i+1)) != result.end() && prevStoneIndex->second.find(prevStonePos) != prevStoneIndex->second.end())){
if(n == stones.size() - 1){
return true;
}
result[i].insert(stones[n]);
int nowCanReach = stones[n] + i + 1;
if(nowCanReach > maxReach)
maxReach = nowCanReach;
int nowJump = i+1;
if(nowJump > maxJumpUnit)
maxJumpUnit = nowJump;
}
}
}
return false;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.