C++ DP


  • 0
    G
    class Solution {
    public:
        
        bool canCross(vector<int>& stones) {
            int n=(int)stones.size();
            if(stones[1] != 1) {
                return false;
            }
            
            vector<set<int>> dp(n, set<int>());
            map<int, int> mapPosIndex;
            
            dp[0]=set<int>({0});
            dp[1]=set<int>({1});
            
            for(int i=0; i < n; i++) {
                mapPosIndex[stones[i]]=i;
            }
            
            bool flag=false;
            for(int j=1; j < n; j++) {
                int pos = stones[j];
                for(auto it:dp[j]) {
                    int i=it;
                    for(int jump=i-1; jump <= i+1; jump++) {
                        if(jump <= 0)
                            continue;
                        int nextPos = pos + jump;
                        if(!mapPosIndex.count(nextPos)) {
                            continue;
                        }
                        int nextIndex=mapPosIndex[nextPos];
                        dp[nextIndex].insert(jump);
                    }
                }
            }
            
            if(dp[n-1].size() > 0) {
                flag=true;
            }
            
            return flag;
        }
    };
    

Log in to reply
 

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