<p>You are given an array of <strong>distinct</strong> positive integers locations where <code>locations[i]</code> represents the position of city <code>i</code>. You are also given integers <code>start</code>, <code>finish</code> and <code>fuel</code> representing the starting city, ending city, and the initial amount of fuel you have, respectively.</p>

<p>At each step, if you are at city <code>i</code>, you can pick any city <code>j</code> such that <code>j != i</code> and <code>0 &lt;= j &lt; locations.length</code> and move to city <code>j</code>. Moving from city <code>i</code> to city <code>j</code> reduces the amount of fuel you have by <code>|locations[i] - locations[j]|</code>. Please notice that <code>|x|</code> denotes the absolute value of <code>x</code>.</p>

<p>Notice that <code>fuel</code> <strong>cannot</strong> become negative at any point in time, and that you are <strong>allowed</strong> to visit any city more than once (including <code>start</code> and <code>finish</code>).</p>

<p>Return <em>the count of all possible routes from </em><code>start</code> <em>to</em> <code>finish</code>. Since the answer may be too large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

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

<pre>
<strong>Input:</strong> locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
<strong>Output:</strong> 4
<strong>Explanation:</strong> The following are all possible routes, each uses 5 units of fuel:
1 -&gt; 3
1 -&gt; 2 -&gt; 3
1 -&gt; 4 -&gt; 3
1 -&gt; 4 -&gt; 2 -&gt; 3
</pre>

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

<pre>
<strong>Input:</strong> locations = [4,3,1], start = 1, finish = 0, fuel = 6
<strong>Output:</strong> 5
<strong>Explanation:</strong> The following are all possible routes:
1 -&gt; 0, used fuel = 1
1 -&gt; 2 -&gt; 0, used fuel = 5
1 -&gt; 2 -&gt; 1 -&gt; 0, used fuel = 5
1 -&gt; 0 -&gt; 1 -&gt; 0, used fuel = 3
1 -&gt; 0 -&gt; 1 -&gt; 0 -&gt; 1 -&gt; 0, used fuel = 5
</pre>

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

<pre>
<strong>Input:</strong> locations = [5,2,1], start = 0, finish = 2, fuel = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong> It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.
</pre>

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

<ul>
	<li><code>2 &lt;= locations.length &lt;= 100</code></li>
	<li><code>1 &lt;= locations[i] &lt;= 10<sup>9</sup></code></li>
	<li>All integers in <code>locations</code> are <strong>distinct</strong>.</li>
	<li><code>0 &lt;= start, finish &lt; locations.length</code></li>
	<li><code>1 &lt;= fuel &lt;= 200</code></li>
</ul>

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        """
        Solve using DP, this is a counting question.

        The state of our DP is the starting location and also how much
        fuel is left. Return dp(start, fuel) to get the result i.e.
        begin at the start location with full fuel.

        Let dp[i, f] be the number of ways to reach the finish if we
        begin at node i with f fuel remaining.

        Base-cases are:
            If f < 0 then the answer is 0
            Also for i == finish and fuel == 0, the answer is 1
        
        The recurrence relation is:
            dp[i, f] = sum([dp[j, f-fuel_cost] for all j != i])
            The number of ways to get from i to finish is equal
            to the sum of pathways to other nodes that reach the
            finish.
        """
        mod = 10 ** 9 + 7
        n = len(locations)

        dp_cache = {}
        def dp(i: int, fuel: int) -> int:
            """
            Counts how many paths there are starting at i to finish
            with a certain amount of fuel remaining. 
            """
            if fuel < 0: # Recursion-base case, if we reach a point of
                # negative fuel then there are no paths to the finish 
                return 0
            
            ans = dp_cache.get((i, fuel), None)
            if ans is None:
                # We can continue on if we reach the finish state, we just have 
                # to reach it again later on as well. Reaching it now we record
                # a path has reached it and add to it the number of paths that
                # will also reach it again circling back again
                ans = 1 if i == finish else 0
                ans += sum([dp(j, fuel - abs(locations[i]-locations[j])) for j in range(n) if i != j]) % mod
                dp_cache[(i, fuel)] = ans
            return ans

        return dp(start, fuel)

        
21700