Simple Dynamic Programming (Memoization) Solution. Well explained.
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst I was thinking about recursion because when we are at any position index \'i\' we
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst I was thinking about recursion because when we are at any position index \'i\' we have n - 1 number of choices to explore. But with recursion the Time Complexity will become exponential that is O(n ^ fuel). So as to reduce the Time Complexity with a sort of similar approach, I started looking for repeating subproblems, below is the explanation of what kind of repeating subproblems are there and how to build the final answer from these subproblems:\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAbout the workings of the function countRoutes:\nI am defining my subproblems as dp[i][j] = number of ways we can reach to the locations[j] whenever the amount of fuel left at this location is equal to i.\nAs you can see the base case at line 29 is dp[fuel][start] = 1.\nSo by the definition of 2d vector dp you must know that all we need is the sum of routes to finish whenever the traveller has i fuel where 0 <= i <= fuel.\nAnd that sum will be stored in the variable allPossibleRoutes which is calculated as follows:\n\nNow looking at the workings of the function countingRoutes:\nAll about the variables:\ncurrPosIdx signifies that the traveller is standing at locations[currPosIdx] at this instance.\nremFuel signifies the remaining fuel at this location.\nSuppose if someone is at locations[currPosIdx] with remaining Fuel as remFuel then they must have reached here from locations[i] when they had the remaining fuel as remFuel + abs( locations[i] - locations[currPosIdx] ) at locations[i] where i != currPosIdx.\nThus we must perform the summation dp[remFuel + abs( locations[i] - locations[currPosIdx] )][i] in order to get to the answer of current subproblem.\nIf we need to more fuel than maxFuel in order to go from locations[i] to locations[currPosIdx] then the underlying travel is not possible.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O( n * fuel )$$\nn = number of locations.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O( n * fuel )$$\nn = number of locations.\n\n# Code\n```\n\nclass Solution {\n    int mod = 1e9 + 7;\n    \n    int countingRoutes(vector<int>& locations, int remFuel, int currPosIdx, int n, vector<vector<int>>& dp, int maxFuel) {\n        \n        if(dp[remFuel][currPosIdx] != -1) {\n            return dp[remFuel][currPosIdx];\n        }\n        \n        dp[remFuel][currPosIdx] = 0;\n        for(int i=0; i<n; i++) {\n\n            dp[remFuel][currPosIdx] = ( (remFuel + abs( locations[i] - locations[currPosIdx] ) <= maxFuel) and (i != currPosIdx) ) ? ((  (long long) dp[remFuel][currPosIdx] + (long long) countingRoutes(locations, remFuel + abs( locations[i] - locations[currPosIdx] ), i, n, dp, maxFuel)  ) % mod) : dp[remFuel][currPosIdx];\n\n        }\n\n        return dp[remFuel][currPosIdx];\n    }\n\n\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n = locations.size();\n        \n        vector<vector<int>> dp( fuel + 1 , vector<int>( n , -1 ) );  \n        \n        dp[fuel][start] = 1;\n        \n        int allPossibleRoutes = 0;\n        for(int i=0; i<=fuel; i++) {\n            dp[i][finish] = countingRoutes( locations, i, finish, n, dp, fuel );\n            int temp = dp[i][finish];\n            allPossibleRoutes = ( (long long) allPossibleRoutes + (long long) temp ) % mod;\n        }\n\n\n        return allPossibleRoutes;\n    }\n\n    \n};\n\n\n```
['Dynamic Programming', 'Memoization', 'C++']