Python by DFS + DP [w/ Visualization] 有中文解題影片
\u4E2D\u6587\u8A73\u89E3 \u89E3\u984C\u5F71\u7247\nTutorial video in Chinese\n\n\n\n\n\n\n\n\nPython by DFS + DP memoization ( with python built-in decorator @l
[\u4E2D\u6587\u8A73\u89E3 \u89E3\u984C\u5F71\u7247\nTutorial video in Chinese](https://www.youtube.com/watch?v=q3OEj1FaCTs)\n\n\n![image.png](https://assets.leetcode.com/users/images/cbba8aa2-f4a7-4e87-a7b2-f2f3f35d9d66_1687778398.4778624.png)\n\n![image.png](https://assets.leetcode.com/users/images/b0fb7db8-10a9-49c7-b802-9ed78a630fd4_1687778425.6151123.png)\n\n\n\nPython by DFS + DP memoization ( with python built-in decorator [@lru_cache](https://docs.python.org/3/library/functools.html#functools.lru_cache) )\n\n\n\nTime complexity: O( n^2 * feul ) \nWe have O( n * feul ) states, each state need O(n) loop check\n\nSpace complexity: O( n * feul ) on DP table\n\n---\n\n**Implementation**:\n\n```\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        \n        dp = {}\n        cost = lambda cur, dest : abs( locations[cur] - locations[dest] )\n\n        def travel( cur, remain ):\n\n            # Look-up DP table\n            if (cur, remain) in dp:\n                return dp[cur, remain]\n            \n            # Base case\n            if remain < 0 or cost(cur, finish) > remain:\n                dp[cur, remain] = 0\n                return 0\n            \n            # General case, travel to all possible next city\n            # If we start travel from finish, then at least one route\n            route = (cur == finish)\n            for city in range( len(locations) ):\n                route += travel( city, remain - cost(cur, city) ) if city != cur else 0\n\n            dp[cur, remain] = route\n            return route\n\n        # --------------------------------\n        return travel(start, fuel) % (10**9 + 7)\n```\n\n---\n\nShorter equvilent implementation\n\n```\nclass Solution:\n    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n        \n        \n        cost = lambda i, j: abs( locations[i] - locations[j] )\n        \n        # --------------------------------------\n        \n        @lru_cache(None)\n        def dfs(cur, remain_fuel):\n            \n            if remain_fuel < 0:\n                # base case aka stop condition\n                return 0\n            \n            # general case:\n            return sum( dfs(next_city, remain_fuel - cost(cur, next_city) )for next_city in range(len(locations) ) if cur != next_city ) + ( cur == finish )\n\n        # --------------------------------------\n        constant = ( 10 ** 9 + 7 )\n        return dfs(cur=start, remain_fuel=fuel) % constant\n```\n\n---\n\nReference:\n\n[1] [Python official docs about python built-in decorator about memoization @lru_cache](https://docs.python.org/3/library/functools.html#functools.lru_cache)
['Depth-First Search', 'Memoization', 'Python', 'Python3']