# C++ 16ms DP with Map beats 94% so far

• After each jump, in the new stone, I treated the minimum and maximum jump steps from this stone as a pair, first value is the minimum steps, second value is maximum steps. There can be multiple possibilities that jump from previous stones to this stone, so each time a new pair is added, I do like merge intervals

``````class Solution {
public:
bool canCross(vector<int>& stones) {
if(stones.size()==0) return true;

vector<vector<pair<int, int>>> capabilities(stones.size());
capabilities[0].push_back(make_pair(1, 1));

for(int i=0; i<stones.size(); i++){
for(auto& p : capabilities[i]){
for(int j=i+1; j<stones.size(); j++){
if(p.first<=stones[j]-stones[i] && p.second>=stones[j]-stones[i]){
if(capabilities[j].size() > 0 && capabilities[j].back().first<=stones[j]-stones[i]){
capabilities[j].back().first = stones[j]-stones[i]-1;
}
else{
capabilities[j].push_back(make_pair(stones[j]-stones[i]-1, stones[j]-stones[i]+1));
}
}
if(p.second<stones[j]-stones[i]) break;
}
}
}
return capabilities[stones.size()-1].size() > 0;
}
};
``````

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