Python3 - Beats 80% Time and 60% Space ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nWe store the fuel required for going from one location to the other in map of lists whe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe store the fuel required for going from one location to the other in map of lists where the key is the start index and the list contains the fuel required for going from key index to the $i^{th}$ index. \nWe can make use of this dictionary/map to iterate through the locations which will save us time. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSince we can visit the $i^{th}$ city more than once, we cannot stop our iterations once we reach the $finish$ location. The key here is *TO NOT STOP EVEN IF WE HAVE REACHED FINISH* (if we have fuel). \nWe can use dynamic programming with memoization to solve the rest with the $current$ index and $fuel$ remaining as parameters to this dp. \n\n\n# Code\n```\nclass Solution:\n    def countRoutes(self, loc: List[int], start: int, finish: int, fuel: int) -> int:\n        base = 10 ** 9 + 7\n        m = collections.defaultdict(list)\n        n = len(loc)\n        for i in range(n):\n            for j in range(n):\n                m[i].append(abs(loc[j] - loc[i]))\n        \n        @cache\n        def rec(current, fuel):\n            ops = 0\n            if current == finish:\n                ops = 1\n            if fuel == 0:\n                return ops\n            \n            val = m[current]\n            \n            for i in range(len(val)):\n                if i != current and val[i] <= fuel:\n                    ops = (ops + rec(i, fuel - val[i])) % base\n            return ops\n\n        return rec(start, fuel)\n\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python3']