Easy Python3 Solution | DP | Time: 4601 ms (84.64%) | Memory: 20.8 MB (44.74%) 
IntuitionThe problem requires maximizing the score over k days by staying in or traveling between n cities. Each day, you have the choice to either stay in the
# Intuition
The problem requires maximizing the score over `k` days by staying in or traveling between `n` cities. Each day, you have the choice to either stay in the same city or travel to another city. The goal is to optimize these decisions to achieve the maximum score.

# Approach
1. **Dynamic Programming (DP)**:
   - Use a DP table `dp` where `dp[i][j]` represents the maximum score achievable on day `i` if you are in city `j`.
   - On each day, for each city, calculate the score if:
     - You stay in the same city (`stayScore`).
     - You travel from another city to the current city (`travelScore`).

2. **Transition Relation**:
   - `dp[i][j]` is updated as the maximum of:
     - Staying in the same city: `dp[i-1][j] + stayScore[i-1][j]`.
     - Traveling from another city: `max(dp[i-1][k] + travelScore[k][j])`, where `k != j`.

3. **Initialization**:
   - The DP table is initialized to 0 for all cities on day 0 since no scores have been accumulated.

4. **Final Result**:
   - After processing all days, the result is the maximum value in the last row of the DP table (`dp[k][j]`).

# Complexity
- **Time complexity**: 
  - $$O(k \cdot n^2)$$
  - For each of the `k` days, we iterate over `n` cities, and for each city, compute the travel scores from all other `n-1` cities.
- **Space complexity**: 
  - $$O(k \cdot n)$$
  - The DP table requires `k x n` space to store the intermediate scores.

# Code
```python3 []
class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        """
        Finds the maximum score achievable in `k` days while staying or traveling between `n` cities.

        @param n: int - The number of cities.
        @param k: int - The number of days.
        @param stayScore: List[List[int]] - A 2D list where stayScore[i][j] represents the score obtained by staying
                                            in city `j` on day `i`.
        @param travelScore: List[List[int]] - A 2D list where travelScore[i][j] represents the score obtained by
                                              traveling from city `i` to city `j`.
        @return: int - The maximum score achievable after `k` days.
        """
        # Step 1: Initialize a DP table where dp[i][j] represents the maximum score achievable on day `i`
        #         if you are in city `j`.
        dp = [[0] * n for _ in range(k + 1)]  # Rows represent days, columns represent cities.

        # Step 2: Iterate through the days from day 1 to day `k`.
        for i in range(1, k + 1):
            # Step 3: For each city `j`, calculate the maximum score on day `i` if you stay in or travel to `j`.
            for j in range(n):
                # Case 1: Stay in the same city `j`.
                dp[i][j] = dp[i - 1][j] + stayScore[i - 1][j]

                # Case 2: Travel to city `j` from any other city `k`.
                #         Compute the score for traveling from each city `k` (where `k != j`) to city `j`.
                alltravel = [dp[i - 1][k] + travelScore[k][j] for k in range(n) if k != j]
                if alltravel:
                    # Update the maximum score for city `j` on day `i` if traveling yields a higher score.
                    dp[i][j] = max(dp[i][j], max(alltravel))

        # Step 4: Return the maximum score achievable on the last day across all cities.
        return max(dp[-1])
        
```
['Dynamic Programming', 'Python3']