Python3, BEATS 100% RUNTIME AND MEMORY, O(fuel^2)
Intuition\nThis problem can be reduced substancially. We don\'t actually care about the array locations, only the values in it that are within Fuel of the start
# Intuition\nThis problem can be reduced substancially. We don\'t actually care about the array locations, only the values in it that are within **Fuel** of the starting position. The key realization here is that we never need to iterate through locations, we can transform it into a set and then move one fuel at a time, checking the set to see if we hit a new City. \n\nWe can use Dynamic Programming to keep track of how many ways there are to get to each city, for every fuel used, and sum the number of times we get to **End** as we go.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe start from **Start** with a count of **1**, and move one fuel at a time left and right. Everytime we hit another city, we double the count to get to the following position in the same direction, and start another count moving in the opposite direction without doubling.\n\n**I.e.** If we find a city at position 3, and we\'re moving right with a count of 2, update the count moving right at position 4 by 4, and update the count moving left at position 2 by 2.\n\nKeep track of how many times we reach **End** at each iteration, and return the answer once we\'ve used all fuel.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(Fuel^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(Fuel)\n\n# Code\n```\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        start, finish, locations = locations[start], locations[finish], set(locations)\n        if abs(finish-start) > fuel:\n            return 0\n        dp_right, dp_left, answer = {start+1: 1}, {start-1: 1}, (start == finish)\n        for _ in range(fuel):\n            answer += dp_right.get(finish, 0) + dp_left.get(finish, 0)\n            new_dp_left, new_dp_right = {}, {}\n            for i, v in dp_right.items():\n                new_dp_right[i+1] = v\n                if i in locations:\n                    new_dp_right[i+1] += v\n                    new_dp_left[i-1] = v\n            for i, v in dp_left.items():\n                new_dp_left[i-1] = new_dp_left.get(i-1, 0) + v\n                if i in locations:\n                    new_dp_right[i+1] = new_dp_right.get(i+1, 0) + v\n                    new_dp_left[i-1] += v\n            dp_left, dp_right = new_dp_left, new_dp_right\n        return answer % (10**9 + 7)\n```
['Dynamic Programming', 'Python3']