403. Frog Jump

In first place, the solution can be done by recursion and is very straightforward. The tricky part is in line 9 because when gap is less than k, the frog has to jump over the stone as it only has choices of k-1, k and k+1.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      return canJump(stones, 0, 0);  
5:    }  
6:    bool canJump(vector<int> &stones, int pos, int k) {  
7:      for (int i = pos+1; i < stones.size(); i++) {  
8:        int gap = stones[i] - stones[pos];  
9:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
10:        if (gap > k + 1) return false;  
11:        if (canJump(stones, i, gap, dp)) return true;  
12:      }  
13:      return pos == stones.size()-1;  
14:    }  
15:  };  

However, this solution gets TLE. So the memorization is used.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      set<pair<int,int>> dp;  
5:      return canJump(stones, 0, 0, dp);  
6:    }  
7:    bool canJump(vector<int> &stones, int pos, int k, set<pair<int,int>> &dp) {  
8:      if (dp.count(make_pair(pos, k))) return false;  
9:      for (int i = pos+1; i < stones.size(); i++) {  
10:        int gap = stones[i] - stones[pos];  
11:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
12:        if (gap > k + 1) { dp.insert(make_pair(pos, k)); return false; }  
13:        if (canJump(stones, i, gap, dp)) { dp.insert(make_pair(pos, k)); return true; }  
14:      }  
15:      return pos == stones.size()-1;  
16:    }  
17:  };