Frog Jump Solutions in C++

// Source : https://leetcode.com/problems/frog-jump/
// Author : Hao Chen
// Date   : 2016-11-12



class Solution {
public:
    bool canCross_recursion(vector<int>& stones, int curr, int last_jump) {
        for(int i=curr+1; i<stones.size(); i++){
            int next_jump = stones[i] - stones[curr];
            //the minimal jump is far exceed the current node, go to check next node.
            if (next_jump < last_jump - 1) continue;
            //cannot reach this one, then simple reture false;
            if (next_jump > last_jump + 1) return false;
            
            if (i == stones.size() - 1 || canCross_recursion(stones, i, next_jump)) return true;
        }
        return false;
    }
    
    bool canCross_recursion_with_cache(vector<int>& stones, int curr, int last_jump, 
                                        unordered_map<int, unordered_map<int, bool>>& cache) 
    {
        //check the cache is hitted ?
        if (cache.find(curr) != cache.end() && cache[curr].find(last_jump)!=cache[curr].end()) {
            return cache[curr][last_jump];
        }
        
        for(int i=curr+1; i<stones.size(); i++){
            int next_jump = stones[i] - stones[curr];
            if (next_jump < last_jump - 1) continue;
            if (next_jump > last_jump + 1) break;
            if (i == stones.size() - 1 || canCross_recursion_with_cache(stones, i, next_jump, cache)) {
                cache[curr][last_jump] = true;
                return true;
            }
        }
        cache[curr][last_jump] = false;
        return false;
    }
    
    bool canCross_non_recursion(vector<int>& stones) {
        
        // the `jumps` map store the all possible `last jumps`
        unordered_map<int, unordered_set<int>> jumps = {{0, {0}}};
        
        for(int i=0; i<stones.size(); i++) {
            if (jumps.find(i) == jumps.end()){ 
                continue;
            }
            //for each possible last jump which reach the current node.
            for(int last_jump : jumps[i]) {
                //find the next nodes can be reached.
                for (int j=i+1; j < stones.size(); j++) {
                    //ingore the rest node which cannot be reached
                    if (stones[i] + last_jump + 1 < stones[j]) break;
                    
                    // evaluated three possbile jumps for next node 
                    for (int next_jump  = last_jump - 1;   next_jump <= last_jump + 1;  next_jump++)  {
                        if ( stones[i] + next_jump  == stones[j] ) {
                            jumps[j].insert(next_jump);
                        }
                    }
                        
                }
            }
        }
        
        return jumps.find(stones.size()-1)!=jumps.end();
    }
    
    bool canCross(vector<int>& stones) {
        
        //Burst Force solution -- accepted ~500ms
        return canCross_non_recursion(stones);
        
        //DFS with cache solution - accepted ~160ms
        unordered_map<int, unordered_map<int, bool>> cache;
        return canCross_recursion_with_cache(stones, 0, 0, cache);
        
        // Time Limit Error 
        return canCross_recursion(stones, 0, 0); 
        
    }
};