Easy solution || Memoization || Tabularization
Intuition\n Describe your first thoughts on how to solve this problem. \nYou don\'t have to return the paths, which means back tracking is not required. \n\n# A
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nYou don\'t have to return the paths, which means back tracking is not required. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nMaintain a dp with fuel remaining and the position as parameters, if dp with such fuel and position is not inititated, continue the recursion else return the value stored in dp. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nPlease upvote if you find it helpful\n\n# Code\n```\nclass Solution {\npublic:\n// Memoization: \n    int travel(vector<int>& locations,  int pos, int &end, int fuel, vector<vector<int>>& dp){\n        if(fuel == 0 && pos == end) return 1; long long  count = 0; \n       if(dp[fuel][pos] != -1)  return dp[fuel][pos]; \n\n       if(pos == end) count++; \n        for(int i=0; i<locations.size(); i++){\n            if(i == pos || fuel < abs(locations[pos] - locations[i])) continue; \n\n            // if(dp[fuel][pos] == -1) dp[fuel][pos][i] = travel(locations, i, end, fuel - abs(locations[pos] - locations[i]), dp); \n            count += travel(locations, i, end, fuel - abs(locations[pos] - locations[i]), dp); \n            count %= 1000000007; \n        }\n        dp[fuel][pos] = count; \n        return count; \n    }\n\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n       \n       vector<vector<int>> dp(fuel+1, vector<int>(locations.size()+1, -1)); \n\n        // return travel(locations,  start, finish, fuel, dp); \n\n    // Tabularization: \n        for(int i=0; i< locations.size(); i++) dp[0][i] = 0;  \n        dp[0][finish] = 1; \n        for(int i=1; i<=fuel; i++){\n            for(int j=locations.size()-1; j>=0; j--){\n                int count = 0; if(j == finish) count++; \n                for(int k=0; k<locations.size(); k++){\n                    if(k == j || i < abs(locations[j] - locations[k])) continue; \n                    count += dp[i-abs(locations[j] - locations[k])][k]; \n                    count %= 1000000007; \n                }\n                dp[i][j] = count; \n            }\n        }\n\n        return dp[fuel][start]; \n\n        \n        \n\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']