leetcode

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