<p>A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.</p>

<p>Given a list of <code>stones</code>&nbsp;positions (in units) in sorted <strong>ascending order</strong>, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be <code>1</code> unit.</p>

<p>If the frog&#39;s last jump was <code>k</code> units, its next jump must be either <code>k - 1</code>, <code>k</code>, or <code>k + 1</code> units. The frog can only jump in the forward direction.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stones = [0,1,3,5,6,8,12,17]
<strong>Output:</strong> true
<strong>Explanation:</strong> The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stones = [0,1,2,3,4,8,9,11]
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= stones.length &lt;= 2000</code></li>
	<li><code>0 &lt;= stones[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>stones[0] == 0</code></li>
	<li><code>stones</code>&nbsp;is sorted in a strictly increasing order.</li>
</ul>

from collections import defaultdict
class Solution:
    # def canCross(self, stones: List[int]) -> bool:
    #     reached = defaultdict(set)
    #     s = set(stones)
    #     reached[1].add(1)
    #     max_pos = 1
    #     for i in range(1, len(stones)):
    #         if stones[i] > max_pos:
    #             break
    #         for k in reached[stones[i]]:
    #             for jump in (k - 1, k, k + 1):
    #                 pos = stones[i] + jump
    #                 max_pos = max(max_pos, pos)
    #                 if pos in stones and jump > 0:
    #                     reached[pos].add(jump)
    #                 if pos == stones[-1]:
    #                     break

    #     print(reached)
    #     return len(reached[stones[-1]]) > 0

    # def canCross(self, stones: List[int]) -> bool:
    #     memo = {}
    #     s = set(stones)

    #     def dfs(pos, k):
    #         if (pos, k) in memo:
    #             return memo[(pos, k)]
    #         if pos == stones[-1]:
    #             return True
    #         for jump in (k - 1, k, k + 1):
    #             next_pos = pos + jump
    #             if next_pos in stones and jump > 0:
    #                 if dfs(next_pos, jump):
    #                     return True
    #         memo[(pos, k)] = False
    #         return False
    #     return dfs(0, 0)

    def canCross(self, stones: List[int]) -> bool:
        num_stones = len(stones)
        start = stones[1]
        goal = stones[-1]

        if start != 1 or goal > num_stones * (num_stones - 1) // 2:
            return False

        memo = set()
        s = set(stones)

        def dfs(pos, k):
            if (pos, k) in memo:
                return False
            if pos == stones[-1]:
                return True
            if pos > stones[-1] or pos not in s:
                return False
            for jump in (k - 1, k, k + 1):
                next_pos = pos + jump
                if next_pos in s and jump > 0:
                    if dfs(next_pos, jump):
                        return True
            memo.add((pos, k))
            return False
        return dfs(0, 0)
20671