C++, 5-line, recursive DP, very easy to understand


  • 0
    C

    Code can be compressed into 5 lines.

        unordered_map < pair<int, int>, bool, pair_hash > dp_;
    
        bool canCross(vector<int>& stones, int pos = 1, int step = 1) {
            if (dp_.count({ pos, step }))  
                return dp_[{pos, step}];
    
            if (pos >= stones.back()) /* pass the finishing line */
                return dp_[{pos, step}] = pos == stones.back();
    
            if (*lower_bound(stones.begin(), stones.end(), pos) != pos)  /* binary search: reach a pos that has no stone */
                return dp_[{pos, step}] = false;
    
            return dp_[{pos, step}] = canCross(stones, pos + step + 1, step + 1) || 
                                      canCross(stones, pos + step, step) || 
                                      step > 1 && canCross(stones, pos + step - 1, step - 1);
        }
    

    Use the pair object instead of merging pos + (step<<16). The hash for the pair can be created as followed.

    
        struct pair_hash {
            std::size_t operator () (const std::pair<int, int> &p) const { 
                return std::hash<int>{}(p.first) ^ std::hash<int>{}(p.second);
            }
        };

Log in to reply
 

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