Python | DP | Intuitive
\n\n# Approach\n Describe your approach to solving the problem. \n\nMaximum score of day \'i\' for a city \'x\' depends on 2 scenarios:\n\nOn day \'i-1\': \n\n1
\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nMaximum score of day \'i\' for a city \'x\' depends on 2 scenarios:\n\nOn day \'i-1\': \n\n1. Person stayed in the same city \'x\'\n\n2. Person moved from a city \'y\' to city \'x\'.\n\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        \n        dp = [[0]*n for _ in range(k)] # dp[day][city]\n        \n        res = 0\n    \n        for day in range(0, k):\n            \n            for curCity in range(n):\n                \n                samecity = dp[day-1][curCity] if day-1>=0 else 0 \n\n                staying_value = samecity + stayScore[day][curCity]\n                \n                travelling_value = 0\n                for prevCity in range(n):\n                    \n                    othercity = dp[day-1][prevCity] if day-1>=0 else 0\n\n                    travelling_value = max(travelling_value,\n                                           othercity + travelScore[prevCity][curCity])\n                \n                dp[day][curCity] = max(staying_value, travelling_value)\n\n                if day == k-1:\n                    res = max(res, dp[day][curCity])\n\n        \n        \n        return res\n\n\n        \n\n        \n\n        \n\n        \n```
[]