python 3 - top down dp
Pay attention on 2 questions: "how to cache" and "time complexity". Evaluate by reading the constraints.\n\n# Intuition\n2 state variables: where you are, and f
Pay attention on 2 questions: "how to cache" and "time complexity". Evaluate by reading the constraints.\n\n# Intuition\n2 state variables: where you are, and fuel remaining. Sum up all states is ok.\n\nOptimization: if abs(loca[start] - loca[finish]) > fuel -> This means you cannot reach "finish" with the shortest path -> Just return 0 as early exit condition\n\n# Approach\ntop down dp\n\n# Complexity\n- Time complexity:\nO(n * f) -> state variables\n\n- Space complexity:\nO(n * f) -> cache size\n\n# Code\n```\nclass Solution:\n    def countRoutes(self, loca: List[int], start: int, finish: int, fuel: int) -> int:\n        # state = i, fuel -> do loop on each layer\n\n        if abs(loca[start] - loca[finish]) > fuel: return 0 # impossible to reach finish\n\n        @lru_cache(None)\n        def dp(cur, f_remain): # return number of ways\n            if f_remain < 0:\n                return 0\n            \n            res = 1 if cur == finish else 0\n\n            for nxt in range(len(loca)):\n                if nxt == cur:\n                    continue\n                f_need = abs(loca[nxt] - loca[cur])\n                if f_remain >= f_need:\n                    res += dp(nxt, f_remain - f_need)\n            \n            return res\n        \n        return dp(start, fuel) % (10**9 + 7)\n```
['Dynamic Programming', 'Python3']