Python DP O(N^2 * K)
Complexity\n- Time complexity:\nO(N^2 * K)\n\n- Space complexity:\nO(N * K), but can be easily optimized to O(N) (because we only need dp[i + 1][:] when calcula
# Complexity\n- Time complexity:\nO(N^2 * K)\n\n- Space complexity:\nO(N * K), but can be easily optimized to O(N) (because we only need dp[i + 1][:] when calculating dp[i][:])\n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n        dp = [[0 for _ in range(n)] for _ in range(k)]\n\n        for i in range(k - 1, -1, -1):\n            for j in range(n):\n                if i == k - 1:\n                    dp[i][j] = max(stayScore[i][j], max(travelScore[j]))\n                else:\n                    dp[i][j] = max(stayScore[i][j] + dp[i + 1][j], max(\n                        travelScore[j][next_j] + dp[i + 1][next_j] for next_j in range(n)))\n        return max(dp[0])\n        \n```
[]