Python | DP | O(KN^2) time, O(N) space
Complexity\n- Time complexity: O(kn^2) - see the loops\n\n- Space complexity: O(n) - using module 2 trick to only keep the current and previous states\n\n# Code
# Complexity\n- Time complexity: $$O(kn^2)$$ - see the loops\n\n- Space complexity: $$O(n)$$ - using module 2 trick to only keep the current and previous states\n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, n: int, k: int, ss: List[List[int]], ts: List[List[int]]) -> int:\n        dp = [[0] * n for _ in range(2)]  # max score to get if finished in city c\n        for i in range(k):\n            for t in range(n):\n                dp[i % 2][t] = (dp[(i - 1) % 2][t] if i else 0) + ss[i][t]\n                for f in range(n):\n                    dp[i % 2][t] = max(dp[i % 2][t], (dp[(i - 1) % 2][f] if i else 0) + ts[f][t])\n        res = max(dp[(k - 1) % 2])\n        return res\n```
[]