✅Beats 100% || Memo -> Tabulation || C++ || JAVA || PYTHON || Beginner Friendly🔥🔥🔥
Intuition:\nThe Intuition is to count all possible routes from a start city to a finish city, given a certain amount of fuel. It uses a recursive approach with 
# Intuition:\nThe Intuition is to count all possible routes from a start city to a finish city, given a certain amount of fuel. It uses a recursive approach with memoization to optimize the computation.\n\nThe `helper` function performs the main computation. It checks if the remaining fuel is sufficient for each possible move and recursively explores all valid paths. The results of subproblems are stored in a memoization table to avoid redundant computations.\n\nBy using memoization, the code avoids recomputing the same routes multiple times, significantly improving efficiency. The approach enables the algorithm to handle larger inputs by reusing previously computed results, reducing the overall time complexity.\n\n# Explanation:\n1. The `helper` function is a recursive function that performs the main computation for counting all possible routes. It takes the following parameters: `locations` (vector of city locations), `city` (current city index), `finish` (index of the finish city), `remainFuel` (remaining fuel), and `memo` (memoization table).\n2. The function begins by checking if the remaining fuel (`remainFuel`) is negative. If so, it means that the current path is not feasible due to insufficient fuel, and the function returns 0.\n3. Next, the function checks if the result for the current `city` and `remainFuel` combination is already present in the `memo` table. If so, it retrieves and returns the stored result, avoiding redundant computations.\n4. If the result is not available in the `memo` table, the function proceeds to compute it.\n5. The function initializes the `total` variable as 1 if the current `city` is the same as the `finish` city, indicating that a valid route has been found. Otherwise, `total` is initialized as 0.\n6. The function then iterates over all possible `nextCity` indices, representing the cities that can be visited from the current `city`. It skips the current `city` itself.\n7. For each `nextCity`, the function checks if there is enough fuel (`remainFuel`) to travel from the current `city` to the `nextCity`. If so, it recursively calls the `helper` function for the `nextCity` with the updated `remainFuel` (subtracting the fuel consumed for the current move) and adds the returned result to the `total` value.\n8. Before adding the result to `total`, the function takes modulo `MOD` to keep the result within the specified range (1000000007).\n9. Once all possible `nextCity` options have been explored, the function stores the computed `total` result in the `memo` table for the current `city` and `remainFuel` combination. This is done to avoid redundant computations in future recursive calls.\n10. Finally, the function returns the computed `total` result.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    const int MOD = 1000000007;\n\n    int helper(const vector<int>& locations, int city, int finish, int remainFuel, vector<vector<int>>& memo) {\n        if (remainFuel < 0) {\n            return 0;\n        }\n        \n        if (memo[city][remainFuel] != -1) {\n            return memo[city][remainFuel];\n        }\n        \n        int total = city == finish ? 1 : 0;\n        \n        for (int nextCity = 0; nextCity < locations.size(); nextCity++) {\n            if (nextCity != city && remainFuel >= abs(locations[nextCity] - locations[city])) {\n                total = (total + helper(locations, nextCity, finish, remainFuel - abs(locations[nextCity] - locations[city]), memo)) % MOD;\n            }\n        }\n        \n        return memo[city][remainFuel] = total;\n    }\n\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n = locations.size();\n        vector<vector<int>> memo(n, vector<int>(fuel + 1, -1));\n        return helper(locations, start, finish, fuel, memo);\n    }\n};\n```\n```Java []\nclass Solution {\n    private static final int MOD = 1000000007;\n\n    public int helper(int[] locations, int city, int finish, int remainFuel, Integer[][] memo) {\n        if (remainFuel < 0) {\n            return 0;\n        }\n        \n        if (memo[city][remainFuel] != null) {\n            return memo[city][remainFuel];\n        }\n        \n        int total = city == finish ? 1 : 0;\n        \n        for (int nextCity = 0; nextCity < locations.length; nextCity++) {\n            if (nextCity != city && remainFuel >= Math.abs(locations[nextCity] - locations[city])) {\n                total = (total + helper(locations, nextCity, finish, remainFuel - Math.abs(locations[nextCity] - locations[city]), memo)) % MOD;\n            }\n        }\n        \n        return memo[city][remainFuel] = total;\n    }\n\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        int n = locations.length;\n        Integer[][] memo = new Integer[n][fuel + 1];\n        return helper(locations, start, finish, fuel, memo);\n    }\n}\n```\n```Python3 []\nclass Solution:\n    MOD = 1000000007\n\n    def helper(self, locations, city, finish, remainFuel, memo):\n        if remainFuel < 0:\n            return 0\n        \n        if memo[city][remainFuel] is not None:\n            return memo[city][remainFuel]\n        \n        total = 1 if city == finish else 0\n        \n        for nextCity in range(len(locations)):\n            if nextCity != city and remainFuel >= abs(locations[nextCity] - locations[city]):\n                total = (total + self.helper(locations, nextCity, finish, remainFuel - abs(locations[nextCity] - locations[city]), memo)) % self.MOD\n        \n        memo[city][remainFuel] = total\n        return total\n\n    def countRoutes(self, locations, start, finish, fuel):\n        n = len(locations)\n        memo = [[None] * (fuel + 1) for _ in range(n)]\n        return self.helper(locations, start, finish, fuel, memo)\n```\n\n# Tabulation:\n# Code\n```C++ []\nclass Solution {\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {                \n        const int MOD = 1000000007;\n        int n = locations.size();    \n        \n        vector<vector<int>> dp(n, vector<int>(fuel + 1, 0));\n        for (int f = 0; f <= fuel; f++) {\n            dp[finish][f] = 1;\n        }\n        \n        // for each fuel, we calculate all cross between cities\n        for (int f = 0; f <= fuel; f++) {\n            for (int city = 0; city < n; city++) {            \n                for (int nextCity = 0; nextCity < n; nextCity++) {               \n                    if (nextCity != city && f >= abs(locations[nextCity] - locations[city])) {\n                        dp[city][f] = (dp[city][f] + dp[nextCity][f - abs(locations[nextCity] - locations[city])]) % MOD;\n                    }\n                }\n            }            \n        }\n        return dp[start][fuel];\n    }\n};\n```\n```Java []\nclass Solution {\n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        final int MOD = 1000000007;\n        int n = locations.length;\n        \n        int[][] dp = new int[n][fuel + 1];\n        for (int f = 0; f <= fuel; f++) {\n            dp[finish][f] = 1;\n        }\n        \n        for (int f = 0; f <= fuel; f++) {\n            for (int city = 0; city < n; city++) {\n                for (int nextCity = 0; nextCity < n; nextCity++) {\n                    if (nextCity != city && f >= Math.abs(locations[nextCity] - locations[city])) {\n                        dp[city][f] = (dp[city][f] + dp[nextCity][f - Math.abs(locations[nextCity] - locations[city])]) % MOD;\n                    }\n                }\n            }\n        }\n        \n        return dp[start][fuel];\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def countRoutes(self, locations, start, finish, fuel):\n        MOD = 1000000007\n        n = len(locations)\n        \n        dp = [[0] * (fuel + 1) for _ in range(n)]\n        for f in range(fuel + 1):\n            dp[finish][f] = 1\n        \n        for f in range(fuel + 1):\n            for city in range(n):\n                for nextCity in range(n):\n                    if nextCity != city and f >= abs(locations[nextCity] - locations[city]):\n                        dp[city][f] = (dp[city][f] + dp[nextCity][f - abs(locations[nextCity] - locations[city])]) % MOD\n        \n        return dp[start][fuel]\n```\n\n![CUTE_CAT.png](https://assets.leetcode.com/users/images/ecde2368-fdff-4bd1-bb99-cb78044d9238_1687658392.6446245.png)\n\n\n**If you found my solution helpful, I would greatly appreciate your upvote, as it would motivate me to continue sharing more solutions.**
['Dynamic Programming', 'Memoization', 'C++', 'Java', 'Python3']