403. Frog Jump

[namespace-io]

class Solution {
public:
    bool f = false;
    void dfs(int i, int k, vector<int>& stones, set<pair<int, int>>& s){
        if(i < 0) return ;
        if(i == stones.size() - 1) {
            f = true;
            return ;
        }
        
        if(s.find({i, k}) !=  s.end()) return;
        
            
        for(int n = k - 1; n <= k + 1; n++){
            if(n > 0){
                auto it = lower_bound(stones.begin(), stones.end(), stones[i] + n);
                if(it == stones.end()) return ;
                auto j = it - stones.begin();
                if(n > 0 && stones[i] + n == stones[j]) {
                    if(f == true) return;
                    dfs(j, n, stones, s);
                   
                }
            }

        }

        s.insert({i, k});
        
    }
    bool canCross(vector<int>& stones) {
        set<pair<int, int>> s;
        dfs(0, 0, stones, s);
        return f ;
    }
};