leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0403.cpp (688B)

      1 class Solution {
      2     bool dp[2001][2001] = {false};
      3     unordered_map<int, int> um;
      4 
      5     bool rec(const vector<int> &stones, int idx = 0, int k = 0) {
      6         if (idx == stones.size() - 1) return true;
      7         if (dp[k][idx]) return false;
      8         dp[k][idx] = true;
      9 
     10         for (int jmp = k + 1; jmp >= k - 1 && jmp > 0; jmp--) {
     11             if (um.count(stones[idx] + jmp)) {
     12                 if (rec(stones, um[stones[idx] + jmp], jmp)) return true;
     13             }
     14         }
     15 
     16         return false;
     17     }
     18 
     19   public:
     20     bool canCross(const vector<int> &stones) {
     21         for (int i = 0; i < stones.size(); i++)
     22             um.insert({stones[i], i});
     23         return rec(stones);
     24     }
     25 };