DFS with memoization and binary search with explanation (C++)


  • 0
    A

    Search for the last stone in a depth-first approach. You need two important arguments with every recursive call:

    • The frog's current stone index (idx)
    • The frog's last jump (k)

    Since the stone positions array is sorted, you can search for target values ( stones[idx]+k, stones[x]+k-1, stones[x]+k+1) using binary search (instead of looping iteratively. Last optimization is to save the results of each subtree into memoization table to avoid re-computation.

    class Solution{
    
    unordered_map<int, bool> dp;
    
    public:
        bool canCross(vector<int>& stones) {
    		return canReach(0, 0, stones);
        }
    
        bool canReach(int idx, int k, vector<int>& stones)
        {
        	int key = idx | k << 11;
        	//if we evaluated the [key|k] subtree before, return value
        	if(dp.find(key) != dp.end())
        		return dp[key];
    
        	//landing on the last stone
        	if(idx == stones.size()-1)
        		return true;
    
        	bool result = false;
        	//the target value i'm looking for next
        	int target = stones[idx]+k;
    
        	//binary_search for 'target'
        	int future_stone_idx = binary_search (idx+1, target, stones); 
        	if(future_stone_idx != -1){
        		result = canReach(future_stone_idx, k, stones);
        		dp[key] = result;
        		if(result)
        			return true;
        	}
        	
        	//binary_search for 'target-1'
        	future_stone_idx = binary_search (idx+1, target-1, stones);
        	if(future_stone_idx != -1){
        		result = canReach(future_stone_idx, k-1, stones);
        		dp[key] = result;
        		if(result)
        			return true;
        	}
    
        	//binary_search for 'target+1'
        	future_stone_idx = binary_search (idx+1, target+1, stones);
        	if(future_stone_idx != -1){
        		result =  canReach(future_stone_idx, k+1, stones);
        		dp[key] = result;
        		if(result)
        			return true;
        		}
    		
    		//dead end ... no subtree yielded true; 
    		return dp[key]=false;
        }
    
        int binary_search(int idx, int target, vector<int>& stones)
        {
        	int start=idx, end=stones.size()-1; 
        	while(start<=end)  	{
        		int mid= start+((end-start)/2);
        		if(stones[mid] == target)
        			return mid;
        		else
        		{
        			if(target<stones[mid])
        				end=mid-1;
        			else
        				start=mid+1;
        		}
        	}
        	return -1;
        }
    };
    

Log in to reply
 

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