[Python] Simple Top-down DP solution with explanation - O(fuel*N^2)
Idea\n\nWe can use DP to solve this problem.\n\ndp(i, k) means we are currently at locations[i] and we have k fuels left. \n\nThe transition function is:\n\n- d
**Idea**\n\nWe can use DP to solve this problem.\n\n`dp(i, k)` means we are currently at `locations[i]` and we have `k` fuels left. \n\nThe transition function is:\n\n- `dp(i, k) = (i == finish) + sum(dp(j, k - dist(i, j)))` for all valid next location `j`\'s.\n\nHere `(i == finish)` means:\n\n - we reached the ending city, possible routes ++\n - note that we don\'t stop here; we can keep exploring other cities and come back later\n\nAll valid next location `j`\'s means:\n\n- `j != i`\n- `k - dist(i, j) >= 0`\n\n <br />\n\n**Complexity**\n\nTime complexity: `O(fuel*N^2)`\nSpace complexity: `O(fuel*N)`\n\n<br />\n\n**Python**\n```Python\nclass Solution:\n    def countRoutes(self, locations, start, finish, fuel):\n        n = len(locations)\n        MOD = 10**9 + 7\n        \n        @lru_cache(None)\n        def dp(i, k):\n            if k < 0:\n                return 0\n            ans = 1 if i == finish else 0\n            for j in range(n):\n                if i == j:\n                    continue\n                ans += dp(j, k - abs(locations[i] - locations[j]))\n            return ans % MOD\n                \n        return dp(start, fuel)\n```\n\n<br />\n\n`dp(i, k)` can be "simplified" as:\n```Python\n@lru_cache(None)\ndef dp(i, k):\n\treturn (i == finish) + sum(dp(j, k - abs(locations[i] - locations[j])) for j in range(n) if i != j) % MOD if k >= 0 else 0\n```
[]