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

  • 0

    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 {
        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;
                                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;

Log in to reply

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