A frog is crossing a river. The river is divided into some number of 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 can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

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

&nbsp;
Example 1:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: 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:

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.


&nbsp;
Constraints:


	2 &lt;= stones.length &lt;= 2000
	0 &lt;= stones[i] &lt;= 231 - 1
	stones[0] == 0
	stones&nbsp;is sorted in a strictly increasing order.


class Solution:
    def possible(self, i, n, stones, pos, allowedJumps):
        if i == n - 1:
            return True
        key = tuple([i] + allowedJumps)
        if key in self.cache:
            return self.cache[key]
        for jump in allowedJumps:
            if jump > 0 and stones[i] + jump in pos:
                if self.possible(pos[stones[i] + jump], n, stones, pos, [jump - 1, jump, jump + 1]):
                    self.cache[key] = True
                    return True
        self.cache[key] = False
        return False

    def canCross(self, stones: List[int]) -> bool:
        n = len(stones)
        pos = {}
        for i, stone in enumerate(stones):
            pos[stone] = i
        self.cache = {}
        return self.possible(0, n, stones, pos, [1])
class Solution {
    static boolean flag = false;   // If flag is true no more operations in recursion, directly return statement
    public boolean canCross(int[] stones) {
        int i = 0; // starting stone
        int k = 1; // starting jump
        flag = false; 
        return canBeCrossed(stones, k, i);
    }
    
    public boolean canBeCrossed(int[] stones, int k, int i){
        if(!flag){ // If flag is false 
        if(stones[i] + k == stones[stones.length - 1]){ // If frog do 'k' jump from current stone lands on last stones, no more recusive calls and return true
            flag = true;
            return true;
        }
		// If frog do 'k' jump from current stone crosses last stone or not able to reach next stone
		//return false
        if((stones[i] + k > stones[stones.length - 1]) || (stones[i]+k<stones[i+1])) return false;
        int temp = i+1; // identify which next stone frog can reach
		//Find untill which stone frog can jump 
		//So jump from current stone not greater than next possible stone exit loop
        while(stones[i]+k > stones[temp]) temp++;
		//If loop exited 2 condition possible
		//jump from current stone is reached next possible stone
		//or not
		
		//If next possible stone reached
		//then do all possible jumps from this stone 
		//the current stone is 'temp'
		//possible jumps are 'k-1', k, 'k+1'
        if(stones[i]+k == stones[temp]) return (canBeCrossed(stones, k+1, temp) || canBeCrossed(stones, k, temp) || canBeCrossed(stones,k-1,temp));
		
		//If next possible stone not reached means jump from the current stone can't reach any stone
		//hence return false
        else return false;
    }
        else return true;
    }
}
class Solution {
public:
    bool canCross(vector<int>& stones) {
       unordered_map<int,bool>mp; //to see the position where stone is present
       for(int i=0;i<stones.size();i++)
       {
           mp[stones[i]]=true;
       }
       int stone=1; //current stone
       int jump=1; //jump made
       int last_stone=stones[stones.size()-1]; //last stone on which frog will land to cross river
       map<pair<int,int>,bool>dp;
       return fun(mp,stone,jump,dp,last_stone);
    }
    bool fun( unordered_map<int,bool>&mp,int stone,int jump,map<pair<int,int>,bool>&dp,int &ls)
    {
        if(stone==ls) //reached last stone
        {
            return true;
        }
        if(mp.find(stone)==mp.end()) //stone is not present
        {
            return false;
        }
        if(dp.find({stone,jump})!=dp.end())
        {
            return dp[{stone,jump}];
        }
        bool jump1=false;
        bool jump2=false;
        bool jump3=false;
        if((stone+jump-1)>stone) //can take jump of k-1 units
        {
            jump1=fun(mp,stone+jump-1,jump-1,dp,ls);
        }
        if((stone+jump)>stone) //can take jump of k units
        {
            jump2=fun(mp,stone+jump,jump,dp,ls);
        }
        if((stone+jump+1)>stone) //can take jump of k+1 units
        {
            jump3=fun(mp,stone+jump+1,jump+1,dp,ls);
        }
        dp[{stone,jump}]=jump1 or jump2 or jump3;
        return dp[{stone,jump}];
    }
};
var canCross = function(stones) {
    let hash = {};
    function dfs(idx = 0, jumpUnits = 0) {
        let key = `${idx}-${jumpUnits}`;
        if (key in hash) return hash[key];
		
        if (idx === stones.length - 1) return true;
        if (idx >= stones.length) return false;
		
        let minJump = jumpUnits - 1, maxJump = jumpUnits + 1;
        for (let i = idx + 1; i < stones.length; i++) {
            let jump = stones[i] - stones[idx];
            if (jump >= minJump && jump <= maxJump) {
                if (dfs(i, jump)) return hash[idx] = true;
            } else if (jump > maxJump) break;
        } return hash[key] = false;
    }
    return dfs();
};
Frog Jump