[Python3] top-down dp
Define fn(n, x) as the count of possible routes from n to finish with x fuel left. \n\n\nclass Solution:\n    def countRoutes(self, locations: List[int], start:
Define `fn(n, x)` as the count of possible routes from `n` to `finish` with `x` fuel left. \n\n```\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        \n        @lru_cache(None)\n        def fn(n, x): \n            """Return all possible routes from n to finish with x fuel."""\n            if x < 0: return 0 # not going anywhere without fuel \n            ans = 0\n            if n == finish: ans += 1\n            for nn in range(len(locations)): \n                if nn != n: ans += fn(nn, x-abs(locations[n] - locations[nn]))\n            return ans \n        \n        return fn(start, fuel) % 1_000_000_007\n```
['Python3']