C++| Beats 100%| Approch Explained✅
Intuition\nPlease upvote :)\n\n# Approach\nWe\'ll maintain two changing variable at any recursion call. One will be the current city we are in and another will 
# Intuition\nPlease upvote :)\n\n# Approach\nWe\'ll maintain two changing variable at any recursion call. One will be the current city we are in and another will be current fuel that we have. We\'ll intialize a variable ans which will be 0 if the current city is not the finish city. However if the current city is finish city then we initialize the ans variable to 1 as that path should be added to answer. Then we\'ll run a loop from city 0 to city 1 and if the city i is not equal to current city and if current fuel is more than the fuel needed to travel between those two cities then we\'ll make a recursion call and add that answer from recursion call to the ans variable. In the end we\'ll return ans variable.\n\nHowever we\'ll have to memoize this solution because it will lead to repetitive recursion calls. For example we\'ll be able to reach a particular city with multiple paths and be left with same fuel. So this will lead to repetitive calls. COnsider this array [1,2,3,5] and fuel = 10 and start city as 0. SO we\'ll be able to reach city 2 via city 0->1->2 and left with 8 unit fuel. We can also reach city 2 via 0->2 and left with fuel 8. THis will lead to repetitive calls.\n\n# Complexity\n- Time complexity:\nO(N^2)\n\n- Space complexity:\nO(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));  \n        \n        return solve(start, finish, fuel, locations);\n    }\nprivate:\n    vector<vector<int>> dp;  \n    const int Mod = 1e9 + 7;  \n    int solve(int currCity, int endCity, int fuel, const vector<int>& locations){\n        if(fuel < 0) return 0;  \n        if(~dp[fuel][currCity]) \n            return dp[fuel][currCity];  \n\n        int ans = (currCity == endCity);  \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)) % Mod;\n               \n            }\n        return dp[fuel][currCity] = ans;  \n    }\n};\n```
['C++']