# C++ Pure recursive solution but it's is fast (16 ms)

• The key point for this short time is that I scan the stones input first and find the max gap first, and use n(n+1)/2 formula to test whether we can jump across it at that moment.
I tried to use DP[1100][1100] based on previous stone and current stone, which implies last jump distance, but it doesn't shorten the time.

``````class Solution {
public:
bool canCross(vector<int>& stones) {
if(stones.size() < 2 || stones[1] != 1) return false;
int maxGap = 0, maxGapIndex = 0;
for(int i = 1; i < stones.size(); ++i) {
if(stones[i]-stones[i-1] > maxGap) {
maxGap = stones[i]-stones[i-1];
maxGapIndex = i;
}
}
if(maxGap > (maxGapIndex)*(maxGapIndex+1)/2) return false;  //index starts with 0, so to stones[3] we have 3 jumps max
return dfs(stones, 0, 1);
}
bool dfs(vector<int>& stones, int prevLoc, int curLoc) {
// if(curLoc == stones.size()-1) {
//     return true;
// }
int lastJump = stones[curLoc]-stones[prevLoc];
if( (stones[curLoc]+lastJump == stones.back()) || (stones[curLoc]+lastJump-1 == stones.back())
|| (stones[curLoc]+lastJump+1 == stones.back()) ) {
return true;
}
auto it = lower_bound(stones.begin(), stones.end(), stones[curLoc]+lastJump);
if(it != stones.end() && *it == stones[curLoc]+lastJump) {
if( dfs(stones, curLoc, it-stones.begin())) return true;
}
if(lastJump != 1) {
it = lower_bound(stones.begin()+curLoc, stones.end(), stones[curLoc]+lastJump-1);
if(it != stones.end() && *it == stones[curLoc]+lastJump-1) {
if( dfs(stones, curLoc, it-stones.begin())) return true;
}
}
it = lower_bound(stones.begin()+curLoc, stones.end(), stones[curLoc]+lastJump+1);
if(it != stones.end() && *it == stones[curLoc]+lastJump+1) {
if( dfs(stones, curLoc, it-stones.begin()))  return true;
}
return false;
}
};``````

• Modified version with memorization but no early-gap-detection, 56 ms

``````class Solution {
private:
int maxGap, maxGapIndex;
char pass[1100][1100];
public:
bool canCross(vector<int>& stones) {
if(stones.size() < 2 || stones[1] != 1) return false;
// maxGapIndex = 0;
// maxGap = 0;
// for(int i = 1; i < stones.size(); ++i) {
//     if(stones[i]-stones[i-1] > maxGap) {
//         maxGap = stones[i]-stones[i-1];
//         maxGapIndex = i;
//     }
// }
// if(maxGap > (maxGapIndex)*(maxGapIndex+1)/2) return false;  //index starts with 0, so to stones[3] we have 3 jumps max
return dfs(stones, 0, 1);
}
bool dfs(vector<int>& stones, int prevLoc, int curLoc) {
if(pass[prevLoc][curLoc] == -1 ){
return false;
}
int lastJump = stones[curLoc]-stones[prevLoc];
if( (stones[curLoc]+lastJump == stones.back()) || (stones[curLoc]+lastJump-1 == stones.back())
|| (stones[curLoc]+lastJump+1 == stones.back()) ) {
return true;
}
for(int jump = lastJump -1; jump <= lastJump+1; ++jump) {
if(jump == 0) continue;
auto it = lower_bound(stones.begin(), stones.end(), stones[curLoc]+jump);
if(it != stones.end() && *it == stones[curLoc]+jump) {
if( dfs(stones, curLoc, it-stones.begin())) return true;
}
}
pass[prevLoc][curLoc] = -1;
return false;
}
};``````

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