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

• 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;
}
};
``````

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