<p>A certain bug&#39;s home is on the x-axis at position <code>x</code>. Help them get there from position <code>0</code>.</p>

<p>The bug jumps according to the following rules:</p>

<ul>
	<li>It can jump exactly <code>a</code> positions <strong>forward</strong> (to the right).</li>
	<li>It can jump exactly <code>b</code> positions <strong>backward</strong> (to the left).</li>
	<li>It cannot jump backward twice in a row.</li>
	<li>It cannot jump to any <code>forbidden</code> positions.</li>
</ul>

<p>The bug may jump forward <strong>beyond</strong> its home, but it <strong>cannot jump</strong> to positions numbered with <strong>negative</strong> integers.</p>

<p>Given an array of integers <code>forbidden</code>, where <code>forbidden[i]</code> means that the bug cannot jump to the position <code>forbidden[i]</code>, and integers <code>a</code>, <code>b</code>, and <code>x</code>, return <em>the minimum number of jumps needed for the bug to reach its home</em>. If there is no possible sequence of jumps that lands the bug on position <code>x</code>, return <code>-1.</code></p>

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

<pre>
<strong>Input:</strong> forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
<strong>Output:</strong> 3
<strong>Explanation:</strong> 3 jumps forward (0 -&gt; 3 -&gt; 6 -&gt; 9) will get the bug home.
</pre>

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

<pre>
<strong>Input:</strong> forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
<strong>Output:</strong> -1
</pre>

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

<pre>
<strong>Input:</strong> forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
<strong>Output:</strong> 2
<strong>Explanation:</strong> One jump forward (0 -&gt; 16) then one jump backward (16 -&gt; 7) will get the bug home.
</pre>

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

<ul>
	<li><code>1 &lt;= forbidden.length &lt;= 1000</code></li>
	<li><code>1 &lt;= a, b, forbidden[i] &lt;= 2000</code></li>
	<li><code>0 &lt;= x &lt;= 2000</code></li>
	<li>All the elements in <code>forbidden</code> are distinct.</li>
	<li>Position <code>x</code> is not forbidden.</li>
</ul>

from collections import defaultdict

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        #@lru_cache(maxsize=None)
        memo = {}
        counter = defaultdict(int)
        visited = set([])

        @lru_cache(maxsize=None)
        def dp(pos, was_backward):
            nonlocal memo, counter, visited
            #print((pos, was_backward), visited)
            #print(memo)
            if (pos, was_backward) in visited:
                return -1
            visited.add((pos, was_backward))
            #if (pos, was_backward) in memo:
                #return memo[(pos, was_backward)]
            #counter[pos] = counter[pos] + 1
            #print(list(key for key in counter if counter[key] > 2))
            if pos > x + 8 * b or pos < 0:
                #memo[(pos, was_backward)] = -1
                return -1
            if pos in forbidden:
                #memo[(pos, was_backward)] = -1
                return -1
            if pos == x:
                #memo[(pos, was_backward)] = 0
                return 0

            #print((pos, was_backward) in memo)
            if was_backward == False:
                #print(pos, was_backward)
                if dp(pos + a, False) == -1 and dp(pos - b, True) == -1:
                    #memo[(pos, was_backward)] = -1
                    return -1
                elif dp(pos + a, False) != -1 and dp(pos - b, True) != -1:
                    #memo[(pos, was_backward)] = min(dp(pos + a, False), dp(pos - b, True)) + 1
                    return min(dp(pos + a, False), dp(pos - b, True)) + 1
                else:
                    #memo[(pos, was_backward)] = max(dp(pos + a, False), dp(pos - b, True)) + 1
                    return max(dp(pos + a, False), dp(pos - b, True)) + 1
            else:
                if dp(pos + a, False) == -1:
                    #memo[(pos, was_backward)] = -1
                    return -1
                else:
                    #memo[(pos, was_backward)] = dp(pos + a, False) + 1
                    return dp(pos + a, False) + 1

        return dp(0, False)
        
379