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


  • 0
    S

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

Log in to reply
 

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