```
class Solution(object):
def canCross(self, stones):
memo, stones, last = {}, set(stones), stones[-1]
def helper(pos, jump):
if pos == last: return True
if jump <= 0 or pos not in stones: return False
if (pos, jump) in memo: return memo[pos, jump]
for nex in {jump, jump - 1, jump + 1}:
if helper(pos + nex, nex): return True
memo[pos, jump] = False
return False
return helper(1, 1)
# 39 / 39 test cases passed.
# Status: Accepted
# Runtime: 166 ms
```

Let's talk about complexity. Right off the bat, we can get an easy big-O estimation by considering that we do 3 sub-recursive call at each recursive call, leading to an `O(3^n)`

complexity. However, we can achieve a better time complexity estimation by observing that for each position `pos`

, there are maximum `pos-1`

possible jumps that can lead to position `pos`

. Therefore, we have a recursive tree with at most `1 + 2 + ... + n`

nodes, leading to a complexity of `O(n^2)`

. Space is also `O(n^2)`

since we need to store in `memo`

the results of the negative calls.

Even shorter BFS (iterative):

```
class Solution(object):
def canCross(self, stones):
visits, stones, last, queue = {(1, 1)}, set(stones), stones[-1], [(1, 1)]
for pos, jump in queue:
if pos == last: return True
if jump <= 0 or pos not in stones: continue
for nex in {jump, jump - 1, jump + 1}:
if (pos + nex, nex) not in visits:
visits.add((pos + nex, nex))
queue.append((pos + nex, nex))
return False
```