Easy to understand. Using dynamic programming approach.
Intuition\nThe task involves maximizing a score over several days (k days) by either staying in a particular city or traveling to another. Each city has a speci
# Intuition\nThe task involves maximizing a score over several days (k days) by either staying in a particular city or traveling to another. Each city has a specific score associated with staying (stayScore) or traveling to other cities (travelScore). My first thought is that this problem can be approached with dynamic programming because it involves maximizing cumulative scores across stages (days), where each decision affects the next state.\n\n# Approach\nDefine DP Table: Create a 2D DP table dp[r][i], where r represents the day (starting from the end) and i represents the city. dp[r][i] will store the maximum score possible if starting from city i on day r.\n\nBottom-Up Calculation: Since each day\u2019s decision depends on the potential scores of the subsequent day, we can build our solution from the last day up to the first:\n\n    For each day r (from k-1 to 0), consider each city i.\n    For each city i, check the possible scores if staying in the same city or traveling to other cities m.\n    Update dp[r][i] based on the highest possible score calculated from dp[r + 1][m] (score from the next day) plus either stayScore (for staying) or travelScore (for moving to a new city).\n\nResult: After populating the dp table, the maximum score for the first day across all cities will be the solution. This value represents the best possible score achievable from any city on day 0.\n\n# Complexity\n- Time complexity:\n $$O(k\u22C5n^2)$$, where:\n    $$k$$ is the number of days.\n    $$n$$ is the number of cities. This is due to the nested loop that iterates through each city on each day and considers every possible city-to-city connection.\n\n- Space complexity:\n$$O(k\u22C5n)$$, where:\n$$k$$ is the number of days, and\n$$n$$ is the number of cities.\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        ROWS = k + 1  # Total number of rows, representing days + 1\n        COLS = n  # Total number of cities\n\n        dp = [[0 for _ in range(COLS)] for _ in range(ROWS)]  # DP table to store max scores\n        res = 0\n\n        # Traverse rows from bottom to top (days in reverse order)\n        for r in range(ROWS - 2, -1, -1):\n\n            # Iterate through each city\n            for i in range(COLS):\n\n                # Calculate the score for staying in the current city or traveling to another\n                for m in range(COLS):\n\n                    # If staying in the same city\n                    if m == i:\n                        dp[r][i] = max(dp[r][i], dp[r + 1][m] + stayScore[r][m])\n                    # If traveling to a different city\n                    else:\n                        dp[r][i] = max(dp[r][i], dp[r + 1][m] + travelScore[i][m])\n\n        # Return the maximum score possible on the first day\n        return max(dp[0])\n\n```
[]