Dynamic Programming || Recursion || Memoization |C++
Recursion + Memoization\nHints\n Use dynamic programming to solve this problem with each state defined by the city index and fuel left.\n Since the array contai
# Recursion + Memoization\n*Hints*\n* Use dynamic programming to solve this problem with each state defined by the city index and fuel left.\n* Since the array contains distinct integers fuel will always be spent in each move and so there can be no cycles.\n\n**Process**\n1. we start from the *start* city and iterate over all the locations within our reach with remaining amount of fuel i.e city whose `fuelCost` is less than or equal to the ` fuel` remaining.\n2. Since we can visit a city multiple times (including the `finish` city) we can do not return when our current city is finish city i.e. `idx == finish` rather we increment the `ans` variable.\n3. At last we simply add all the ways to `ans`  by iterating all the cities within our reach recursively.  \n4. Then return the answer.\n\n```\nclass Solution {\npublic:\n    int mod=1e9+7;\n    int dp[105][205];\n    int func(int idx,vector<int>& locations,int finish,int fuel){\n        long long ans=0;\n        if(idx==finish)\n            ans++;\n        \n        if(dp[idx][fuel]!=-1)return dp[idx][fuel];\n        int n=locations.size();\n        \n        for(int i=0;i<n;i++){\n            int fuelCost=abs(locations[i]-locations[idx]);\n           if(fuelCost<=fuel and i!=idx){\n               ans+=func(i,locations,finish,fuel-fuelCost)%mod;\n           }\n        }\n        return dp[idx][fuel]=ans%mod;\n    }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int noOfCities=locations.size();\n        memset(dp,-1,sizeof(dp));\n        int noOfWays=func(start,locations,finish,fuel);\n        return noOfWays;\n    }\n}\n```\n\n**Time complexity**\nRecursion =  O(2^n)\nRecursion + memoization = O(n^2)\n\t\t*n is the number of cities given*\n\t\t\n**Space Complexity - O(n^2)**\n
['Dynamic Programming', 'Recursion', 'Memoization', 'C']