[Python] recursion + @cache
\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n\n        @cache\n        def dfs(i
```\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n\n        @cache\n        def dfs(i, curr):\n            if i == k:\n                return 0\n\n            m = dfs(i + 1, curr) + stayScore[i][curr]\n\n            for dest in range(n):\n                m = max(m, dfs(i + 1, dest) + travelScore[curr][dest])\n                \n            return m\n\n        return max(dfs(0, curr) for curr in range(n))\n```
[]