Frog Jump LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool canCross(vector<int> &stones) {
4
    unordered_map<int, bool> mp; // to see the position where stone is present
5
    for (int i = 0; i < stones.size(); i++) {
6
      mp[stones[i]] = true;
7
    }
8
    int stone = 1;                              // current stone
9
    int jump = 1;                               // jump made
10
    int last_stone = stones[stones.size() - 1]; // last stone on which frog will land to cross river
11
    map<pair<int, int>, bool> dp;
12
    return fun(mp, stone, jump, dp, last_stone);
13
  }
14
  bool fun(unordered_map<int, bool> &mp, int stone, int jump, map<pair<int, int>, bool> &dp,
15
           int &ls) {
16
    if (stone == ls) // reached last stone
17
    {
18
      return true;
19
    }
20
    if (mp.find(stone) == mp.end()) // stone is not present
21
    {
22
      return false;
23
    }
24
    if (dp.find({stone, jump}) != dp.end()) {
25
      return dp[{stone, jump}];
26
    }
27
    bool jump1 = false;
28
    bool jump2 = false;
29
    bool jump3 = false;
30
    if ((stone + jump - 1) > stone) // can take jump of k-1 units
31
    {
32
      jump1 = fun(mp, stone + jump - 1, jump - 1, dp, ls);
33
    }
34
    if ((stone + jump) > stone) // can take jump of k units
35
    {
36
      jump2 = fun(mp, stone + jump, jump, dp, ls);
37
    }
38
    if ((stone + jump + 1) > stone) // can take jump of k+1 units
39
    {
40
      jump3 = fun(mp, stone + jump + 1, jump + 1, dp, ls);
41
    }
42
    dp[{stone, jump}] = jump1 or jump2 or jump3;
43
    return dp[{stone, jump}];
44
  }
45
};