Python Dynamic Programming Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nwe have 3 cities:\n- city1, city2, city3\n\nfor city1, on day 1, best choice would be:\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe have 3 cities:\n- city1, city2, city3\n\nfor city1, on day 1, best choice would be:\n- max( stay_here_points, city2_to_city1_points, city3_to_city1_points)\n\nnow we update the dp:\n- dp[day1][city1] = the max points\n\non day 2 and onwards, we sum previous day\'s points + today\'s points to compare.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nmy first dp \n\n# Complexity\n- Time complexity:  $$O(k*n^2)$$ \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:  $$O(n)$$ \n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(\n        self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]\n    ) -> int:\n\n        dp = [[0] * n for _ in range(k + 1)]\n\n        for day in range(1, k + 1):\n            for city in range(n):\n                stay_points = dp[day - 1][city] + stayScore[day - 1][city]\n                max_travel_points = stay_points\n                for dest in range(n):\n                    # here we want to find the points from other city -> current city\n                    if city == dest:\n                        continue\n                    points_from_other_city_to_cur = dp[day - 1][dest] + travelScore[dest][city]\n                    max_travel_points = max(max_travel_points, points_from_other_city_to_cur)\n                dp[day][city] = max_travel_points\n        return max(dp[-1])\n```
[]