Faster than -✔💚✔92.82% [cpp],75% in [java][Python] -dp, memoization, Recurstion,TC=SC = O(n*fuel)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be solved using dynamic programming. We need to find the count of all p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be solved using dynamic programming. We need to find the count of all possible routes from the start city to the finish city, considering the fuel constraints.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- We\'ll use a recursive function called possibleRoutes to calculate the count of routes from a given city with a certain amount of remaining fuel.\n- The base case for the recursive function is when the remaining fuel becomes negative. \n- In this case, we return 0 since it\'s not possible to continue further.\n- We\'ll use memoization to store the results of subproblems. We\'ll create a 2D array called dp to store the intermediate results. \n- The dimensions of dp are n (number of cities) and fuel+1 (amount of fuel plus one to accommodate for the initial fuel).\n- If the result for the current city and remaining fuel is already calculated and stored in dp, we\'ll return that result directly.\n- If the current city is the finish city, we increment the answer by 1 since we have found a valid route.\n- We\'ll iterate over all possible next cities from the current city and recursively call the possibleRoutes function for each next city, updating the remaining fuel accordingly.\n- Finally, we store the result in dp and return it.\n- In the countRoutes function, we initialize n as the length of the locations array, create the dp array, and call the possibleRoutes function with the start city and initial fuel.\n- The result will be the count of all possible routes from the start to the finish city.\n\n# Complexity\n- Time complexity: **O(n * fuel)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the solution is O(n * fuel), where n is the number of cities and fuel is the maximum amount of fuel. This is because for each city, we iterate over all possible next cities, resulting in a total of n * fuel iterations.\n\n- Space complexity: **O(n * fuel)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity of the solution is O(n * fuel) as well. We use a memoization array (dp) of size n * fuel to store the intermediate results. Additionally, the recursive calls to the possibleRoutes function can have a maximum depth of n, which contributes to the space complexity.\n\n# Code\n```Java []\nclass Solution {\n    int[][] dp; // memoization array\n    int n; // number of cities\n    int finish; // finish city\n\n    public int possibleRoutes(int[] locations, int currCity, int remainingFuel) {\n        if (remainingFuel < 0) {\n            return 0; // base case: not enough fuel to continue\n        }\n        if (dp[currCity][remainingFuel] != -1) {\n            return dp[currCity][remainingFuel]; // return memoized result if available\n        }\n\n        int ans = currCity == finish ? 1 : 0; // increment answer if current city is the finish city\n\n        for (int nextCity = 0; nextCity < n; nextCity++) {\n            if (nextCity != currCity) {\n                // recursively calculate count of routes for each next city\n                ans = (ans + possibleRoutes(locations, nextCity, remainingFuel - Math.abs(locations[currCity] - locations[nextCity]))) % 1000000007;\n            }\n        }\n\n        dp[currCity][remainingFuel] = ans; // store the result in memoization array\n        return ans;\n    }\n\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        n = locations.length;\n        dp = new int[n][fuel + 1]; // create memoization array\n\n        this.finish = finish;\n\n        for (int i = 0; i < n; i++) {\n            Arrays.fill(dp[i], -1); // initialize memoization array with -1\n        }\n\n        return possibleRoutes(locations, start, fuel); // call recursive function\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int n;\n    int finish;\n\n    int possibleRoutes(vector<int>& locations, int currCity, int remainingFuel) {\n        if (remainingFuel < 0) {\n            return 0; // base case: not enough fuel to continue\n        }\n        if (dp[currCity][remainingFuel] != -1) {\n            return dp[currCity][remainingFuel]; // return memoized result if available\n        }\n\n        int ans = currCity == finish ? 1 : 0; // increment answer if current city is the finish city\n\n        for (int nextCity = 0; nextCity < n; nextCity++) {\n            if (nextCity != currCity) {\n                // recursively calculate count of routes for each next city\n                ans = (ans + possibleRoutes(locations, nextCity, remainingFuel - abs(locations[currCity] - locations[nextCity]))) % 1000000007;\n            }\n        }\n\n        dp[currCity][remainingFuel] = ans; // store the result in memoization array\n        return ans;\n    }\n\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        n = locations.size();\n        dp.resize(n, vector<int>(fuel + 1, -1)); // create memoization array\n\n        this->finish = finish;\n\n        return possibleRoutes(locations, start, fuel); // call recursive function\n    }\n};\n\n```\n```Python3 []\nclass Solution:\n    def __init__(self):\n        self.dp = None\n        self.n = 0\n        self.finish = 0\n\n    def possibleRoutes(self, locations: List[int], currCity: int, remainingFuel: int) -> int:\n        if remainingFuel < 0:\n            return 0  # base case: not enough fuel to continue\n\n        if self.dp[currCity][remainingFuel] != -1:\n            return self.dp[currCity][remainingFuel]  # return memoized result if available\n\n        ans = 1 if currCity == self.finish else 0  # increment answer if current city is the finish city\n\n        for nextCity in range(self.n):\n            if nextCity != currCity:\n                # recursively calculate count of routes for each next city\n                ans = (ans + self.possibleRoutes(locations, nextCity, remainingFuel - abs(locations[currCity] - locations[nextCity]))) % 1000000007\n\n        self.dp[currCity][remainingFuel] = ans  # store the result in memoization array\n        return ans\n\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        self.n = len(locations)\n        self.dp = [[-1] * (fuel + 1) for _ in range(self.n)]  # create memoization array\n        self.finish = finish\n\n        return self.possibleRoutes(locations, start, fuel)  # call recursive function\n```\nFound Useful -> **Please Upvote!**
['Array', 'Dynamic Programming', 'C++', 'Java', 'Python3']