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

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

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

Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: 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


Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: 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


Example 3:

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


&nbsp;
Constraints:


	2 &lt;= locations.length &lt;= 100
	1 &lt;= locations[i] &lt;= 109
	All integers in locations are distinct.
	0 &lt;= start, finish &lt; locations.length
	1 &lt;= fuel &lt;= 200


from bisect import bisect_left
from functools import lru_cache
class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        start = locations[start]
        end = locations[finish]
        locations.sort()
        start = bisect_left(locations, start)
        end = bisect_left(locations, end)
        @lru_cache(None)
        def dfs(i, fuel):
            if fuel == 0 and i == end: return 1
            res = 0
            if i == end: res += 1
            j = i-1
            while j>=0 and abs(locations[j]-locations[i]) <= fuel:
                res += dfs(j, fuel-abs(locations[j]-locations[i]))
                j -= 1
            j = i+1
            while j<len(locations) and abs(locations[j]-locations[i]) <= fuel:
                res += dfs(j, fuel-abs(locations[j]-locations[i]))
                j += 1
            return res
        return dfs(start, fuel) % (10**9+7)
/*

Using DFS and Memo :

1. We will start from start pos provided and will dfs travel to each other location .
2. each time we will see if we reach finish , we will increment the result . but we wont stop there if we have fuel left and continue travelling
3. if fuel goes negetive , we will return 0 , as there is no valid solution in that path
4. we will take dp[locations][fuel+1] to cache the result , to avoid recomputing .

*/

class Solution {

    int mod = (int)Math.pow(10,9) + 7 ;
    int[][] dp ;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {

        dp = new int[locations.length][fuel+1] ;

        for(int[] row : dp){
            Arrays.fill(row , -1) ;
        }

        return dfs(locations , start , finish , fuel);
    }

    public int dfs(int[] locations , int cur_location , int finish , int fuel){

        if(fuel < 0){
            return 0 ;
        }

        if(dp[cur_location][fuel] != -1){
            return dp[cur_location][fuel] ;
        }

        int result = 0 ;

        if(cur_location == finish){
            result++ ;
        }

        for(int i=0 ; i<locations.length ; i++){

            if(i == cur_location) continue ;

            int fuel_cost = Math.abs(locations[i] - locations[cur_location]);
            int next_trip = dfs(locations , i , finish , fuel-fuel_cost);
            result += next_trip ;
            result %= mod ;
        }

        dp[cur_location][fuel] = result ;

        return dp[cur_location][fuel] ;
    }
}
class Solution {
public:
    
    int fun(vector<int> &arr , int s , int f , int k , vector<vector<int>> &dp){
        if(k<0) return 0 ;
        if(dp[s][k]!=-1) return dp[s][k] ;
        int ans=0 ;
        if(s==f) ans=1 ;
        for(int i=0 ; i<arr.size() ; i++){
            if(i!=s) ans=(ans+fun(arr,i,f,k-abs(arr[s]-arr[i]),dp))%1000000007;
        }
     return dp[s][k]=ans ;   
    }
    
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        vector<vector<int>> dp(locations.size()+1,vector<int>(fuel+1,-1)) ;
        int ans=fun(locations,start,finish,fuel,dp) ;
        return ans ;
    }
};
var countRoutes = function(locations, start, finish, fuel) {
    const memo = new Array(locations.length+1).fill(0).map(()=>new Array(201).fill(-1));
    
    const dfs = function(cur, f){
        if(f<0) return 0;
        if(memo[cur][f]!=-1) return memo[cur][f];
        let res = (cur==finish);
        for(let i in locations){
            if(i==cur) continue;
            res = (res + dfs(i, f-Math.abs(locations[i]-locations[cur])))%1000000007;
        }
        return memo[cur][f]=res;
    }
    
    return dfs(start, fuel);
};
Count All Possible Routes