C++|  Dynamic Programming (DP) with Memoization |
Intuition\n Describe your first thoughts on how to solve this problem. The code uses dynamic programming with memoization to calculate the number of routes from
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->The code uses dynamic programming with memoization to calculate the number of routes from the start city to the end city within the given fuel limit. The `dp` table stores the computed results to avoid redundant calculations. The `solve` function recursively explores all possible cities and fuel levels to compute the number of routes. The base case handles the situation when the fuel becomes negative, indicating an invalid route. The answer is updated by adding the result of the recursive call and taking the modulo to prevent overflow. Finally, the computed result is stored in the `dp` table and returned.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->The problem at hand is to count the number of routes from a given start city to a target finish city, with a limited amount of fuel. The goal is to find all possible routes that can be taken within the given fuel limit.\n\nTo solve this problem, the code uses a dynamic programming approach with memoization. The `dp` table is used to store the intermediate results of the number of routes for each combination of the current city and the remaining fuel. This helps avoid redundant calculations and improves the efficiency of the algorithm.\n\nThe main function, `countRoutes`, takes in the vector of locations, start city, finish city, and the available fuel as input. It initializes the `dp` table with the necessary dimensions based on the fuel limit. Then, it calls the `solve` function to compute the number of routes.\n\nThe `solve` function is a recursive helper function that takes the current city, the target finish city, the remaining fuel, and the vector of locations as parameters. It first checks if the remaining fuel is negative. If so, it returns 0 since it is not possible to reach the finish city with negative fuel.\n\nNext, it checks if the result for the current state (current city and remaining fuel) is already computed and stored in the `dp` table. If so, it directly returns the precomputed result.\n\nIf the result is not computed, it initializes the answer (`ans`) with 1 if the current city is the same as the finish city. This accounts for the case when the start city is already the finish city, and no further moves are required.\n\nThen, it iterates through all the possible next cities (excluding the current city) and makes a recursive call to `solve` for each next city. In each recursive call, it subtracts the fuel consumed to travel from the current city to the next city. The absolute difference between the locations of the current city and the next city is used to calculate the fuel consumption.\n\nThe result of the recursive call is added to the answer (`ans`) and then takes modulo (`%`) operation with `kMod` to prevent the answer from exceeding the defined limit (1e9 + 7).\n\nFinally, the computed answer is stored in the `dp` table for the current state and returned.\n\nOverall, the approach uses dynamic programming with memoization to break down the problem into smaller subproblems and store their solutions. By leveraging the results of previously computed states, the algorithm avoids redundant calculations and efficiently computes the number of routes from the start city to the finish city within the given fuel limit.\n\n# Complexity\n- Time complexity:  O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(fuel * n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        const int n = locations.size();\n        dp.resize(fuel + 1, vector<int>(n, -1));  // Initialize the memoization table\n        \n        return solve(start, finish, fuel, locations);  // Call the solve function\n    }\nprivate:\n    vector<vector<int>> dp;  // Memoization table to store intermediate results\n    const int kMod = 1e9 + 7;  // Constant to perform modulo operation\n    int solve(int currCity, int endCity, int fuel, const vector<int>& locations){\n        if(fuel < 0) return 0;  // If fuel is negative, return 0 (no valid routes)\n        if(~dp[fuel][currCity])  // If the result for the current state is already computed\n            return dp[fuel][currCity];  // Return the precomputed result\n        \n        int ans = (currCity == endCity);  // Initialize the answer with 1 if we reached the end city, 0 otherwise\n        for(int nextCity = 0; nextCity < locations.size(); ++nextCity)\n            if(nextCity != currCity){\n                ans = (ans + solve(nextCity, endCity, fuel - abs(locations[currCity] - locations[nextCity]), locations)) % kMod;\n                // Recursively calculate the number of routes by moving to the next city\n                // Update fuel by subtracting the distance between the current city and the next city\n                // Add the result to the answer and take modulo to avoid overflow\n            }\n        return dp[fuel][currCity] = ans;  // Store the computed result in the memoization table and return the answer\n    }\n};\n\n```\n![Leetcode.jpeg](https://assets.leetcode.com/users/images/eda12af8-3ecd-4b2b-a3b1-54d576c83ab5_1687668794.922892.jpeg)\n
['C++']