C++ Solution || Dynamic Programming with Memoization || Approach Explained ✅
Intuition\nWe have to count all possible routes and from any city we can go to all other cities so intution is to apply dynamic programming.\n\n# Approach\nWe\'
# Intuition\nWe have to count all possible routes and from any city we can go to all other cities so intution is to apply dynamic programming.\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\n# Code\n```\nclass Solution {\n    private:\n    int mod = 7+1e9;\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        vector<vector<int>>dp(locations.size()+1, vector<int>(fuel+1, -1));\n        return solve(locations, start, finish, fuel, dp);\n    }\n\n    int solve(vector<int>& locations, int current, int& finish, int currentfuel, vector<vector<int>>& dp)\n    {\n        int ans = 0;\n        if(current == finish)\n        {\n            ans = 1;\n        }\n        if(currentfuel == 0)\n        {\n            return ans;\n        }\n        if(dp[current][currentfuel] != -1)\n        {\n            return dp[current][currentfuel];\n        }\n        for(int i = 0;i < locations.size(); i++)\n        {\n            if(i != current && (currentfuel - abs(locations[current]-locations[i])) >= 0)\n            {\n                ans = (ans + (solve(locations, i, finish, currentfuel-abs(locations[current]-locations[i]), dp))%mod)%mod;\n            }\n        }\n        return dp[current][currentfuel] = ans%mod;\n    }\n};\n```\n\n**Do upvote if you understood it !\uD83D\uDE00**
['Dynamic Programming', 'Memoization', 'C++']