C++| Dynamic Programming | Reduced Problem Build Up | Full Explanation | Easy to Understand
Observations \n Describe your first thoughts on how to solve this problem. \n1) We can move from city i to j where i!=j which means we can move from any 1 city 
# Observations \n<!-- Describe your first thoughts on how to solve this problem. -->\n1) We can move from city `i` to `j` where `i!=j` which means we can move from any 1 city to any other city.\n2) The fuel used for such movement would be `abs(locations[i]- locations[j])`.\n3) The contraints on number of cities and and fuel are small.\n`2 <= locations.length <= 100`\n`1 <= fuel <= 200`\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLets first try to solve a reduced version of the problem. Given an array of loactions, where you can move from city `i` to city `j` `i!=j`, return the number of ways of travel with exactly `x` amount of fuel.\nThe fuel used for one such movement would be `abs(locations[i]- locations[j])`.\n\nAfter analysing constraints, to solve this problem, we can start from the city `start`, and try going to all cities from the start, reduce the fuel by the `cost of such movement` and then check if our fuel has become zero.\n\nSince the problem is `with exactly x amount of fuel` we only count the number of ways where we have `fuel=0 and curCity=finish`.\n\nThis gives us the following recurrence:\n```\nf(cur, fuel) :\n    if(cur== finish && fuel==0) return 1\n    if(fuel<0) return 0\n    ways=0\n    for(int j=0 ; j< locations.size(); j++)\n    if(j==i) \n        continue\n    ways+= f(locations, j, finish, fuel- abs(locations[j]- locations[cur]))\n\nreturn ways\n```\n**Point to remember:** If we are able to reach the city `finish` with exactly `x` fuel consumption that is a valid way for the reduced problem.\n\n**OPTIMISING THE RECURRENCE (Memoisation):**\nOn seeing the recurrence we can say that if we have already computed the answer for state `(cur, fuel)` we can store it in a dp table, to provide unnecessary recomputation.\n\nWe can simply use the answer from the dp table and save time.\n\n# FINAL SOLUTION\nThe problem ask to find out all the ways of travel from start to finish. \n\nHence, you can try reaching from start to finish with exact fuel =[0,fuel] and sum all the ways to find the answer to the problem.\n\nUsing the reduced version of the problem, the problem can be mapped to:\n\n`For all x in [0,fuel], calculate the number of ways of reaching from start to finish with exactly x fuel`.\n\nThe answer would be the `sum` of all x computed above. Handle mod when doing summation.\n\n**Point to remember:** There are only N* fuel unique states, where N is the number of cities.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nRecursive: exponential\nMemoisation : O(N* fuel) where N is the number of cities.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nMemosiation: O(N* fuel) where N is the number of cities.\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int mod= 1e9+7;\n    \n    int recur(vector<int>& locations, int cur, int& finish, int fuel, vector<vector<int>>& dp)\n    {\n        if(fuel==0 && cur== finish)\n            return 1;\n        \n        if(cur== locations.size() || fuel <0)\n            return 0;\n        \n        if(dp[cur][fuel]!=-1) return dp[cur][fuel];\n        \n        long long ways=0;\n        for(int j=0; j<locations.size(); j++)\n        {\n            if(cur==j) continue;\n            ways+= recur(locations, j, finish, fuel- abs(locations[j]- locations[cur]),dp)% mod;\n        }\n        \n        return dp[cur][fuel]= ways% mod;\n    }\n    \n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        \n        long long result=0;\n        int n= locations.size();\n        \n        vector<vector<int>> dp(n, vector<int>(fuel+1,-1));\n        \n        for(int i=0;i<=fuel;i++)\n        {\n            result+= recur(locations, start, finish, i,dp)% mod;\n            // cout<<recur(locations, start, finish, i,dp)<<endl;\n        }\n        \n        return result% mod;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']