[Python] standard DP problem; Explained
Define the dp transfermation matrix: dp[i][c] gives the maximum score of ith day at city c. \n\nThus, dp[i+1][c] = max(dp[i][c] + stayScore[i][c], dp[i][x] + tr
Define the dp transfermation matrix: `dp[i][c]` gives the maximum score of `i`th day at city `c`. \n\nThus, `dp[i+1][c]` = `max(dp[i][c] + stayScore[i][c], dp[i][x] + travelScore[x][c])` Note: x can be any city from `0` to `n - 1`.\n\nWe can just loop all the possible cities and find the maximum score.\n\n```\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n        self.dp = collections.defaultdict(list)\n        self.dp[-1] = [0] * n\n        for i in range(k):\n            self.dp[i] = [None] * n\n        self.n = n\n        self.stayScore = stayScore\n        self.travelScore = travelScore\n        \n        ans = 0\n        for i in range(n):\n            ans = max(ans, self.findMaxScore(k - 1, i))\n        return ans\n    \n\n    def findMaxScore(self, i, c):\n        if self.dp[i][c] is None:\n            stay_score = self.findMaxScore(i - 1, c) + self.stayScore[i][c]\n            # can travel from any city b to city c:\n            travel_score = 0\n            for b in range(self.n):\n                if b != c:\n                    travel_score = max(travel_score, self.findMaxScore(i - 1, b) + self.travelScore[b][c])\n        \n            self.dp[i][c] = max(stay_score, travel_score)\n        return self.dp[i][c]\n```
[]