leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0403.cpp (688B)

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