C++|| DP|| WITH EXPLANATION
Approach is simple try all possible cities from a given city and when u reach destination increase the ans. Here there is 2 d dp which is expressed in form of i
Approach is simple try all possible cities from a given city and when u reach destination increase the ans. Here there is 2 d dp which is expressed in form of index and fuel these are the two changing parameters . Dp[index][fuel] represents the number of way to reach the finish starting from current index or the city in the given fuel. So firstly we start from the start city and then from start city we travel to the other possible cities taking fuel . if we dont have fuel we cannot travel from that city to destination city so we return 0. Otherwise if u reach destination just do ans++ and dont stop because from there u can travel to other cities and then again reach the finish city so that has also to be taken into account.\n\n```\nclass Solution {\npublic:\n    int mod= 1e9+7;\n    int helper(int index,int fuel,int finish,vector<int>&locations,vector<vector<int>>&dp){\n        long long ans=0;\n        int n= locations.size();\n        if(fuel<0) return 0;\n        if(dp[index][fuel]!=-1) return dp[index][fuel];\n        if(index== finish) ans++;\n        for(int i=0; i<n; i++){\n            if(i!=index){\n                ans= (ans%mod+ helper(i,fuel-abs(locations[index]- locations[i]),finish,locations,dp)%mod)%mod;\n            }\n        }\n        return dp[index][fuel]= ans;\n    }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n= locations.size();\n        vector<vector<int>>dp(n,vector<int>(fuel+1,-1));\n        return helper(start,fuel,finish,locations,dp);\n        \n    }\n};\n
['Dynamic Programming', 'Memoization', 'C']