Problem Description

You are given two integers, n (the number of cities) and k (the number of days), along with two 2D integer arrays, stayScore and travelScore.

A tourist is planning a journey across n cities, where each city is directly connected to every other city. The journey consists of exactly k days. The tourist can start in any city and has the following choices for each day:

• Stay in the current city: If the tourist stays in city curr on day i, they earn stayScore[i][curr] points.
• Move to another city: If the tourist moves from city curr to city dest, they earn travelScore[curr][dest] points.

Your task is to return the maximum possible points the tourist can earn over the k days.

Intuition

The main objective is to maximize the points gained over the course of k days. We need to consider both staying in the current city and moving to another city. This suggests a dynamic programming approach where we keep track of the maximum points achievable at each stage for each city.

1. Dynamic Programming Table: Define a DP table f where f[i][j] represents the maximum score achievable on day i in city j.

2. Base Case: At day 0, the tourist can start at any city with 0 points, hence f[0][j] = 0 for all j.

3. Transition: For each day i from 1 to k, and each city j:

   • Stay in city j: Add stayScore[i-1][j] to the score from the previous day in the same city.
   • Move from another city h to city j: Add travelScore[h][j] to the score from the previous day in city h.

   Formally, update f[i][j] as: [ f[i][j] = \max(f[i][j], f[i-1][h] + \text{stayScore}[i-1][j]) \quad \text{if}\ j == h ] [ f[i][j] = \max(f[i][j], f[i-1][h] + \text{travelScore}[h][j]) \quad \text{if}\ j \neq h ]

4. Result: After processing all days, the result is the maximum value in f[k], representing the max score obtainable after k days.

This approach efficiently calculates the maximum score by considering both staying and traveling every day, making sure to explore all possibilities and keep the optimal solution.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution employs a dynamic programming (DP) approach to efficiently calculate the maximum points the tourist can earn over the course of k days. Here is a detailed walk-through of the implementation:

1. Initialization:

   • We define a 2D list f where f[i][j] will store the maximum points obtainable on day i in city j.
   • Initialize f with -inf values, since we will be looking for the maximum, and set f[0][j] = 0 for all cities j to denote that the journey starts with zero points.

   f = [[-inf] * n for _ in range(k + 1)]
   f[0] = [0] * n

2. DP Transitions:

   • For each day i from 1 to k and each city j, calculate the maximum points for staying in j or traveling to j from any city h.
   • Use a nested loop: the outer two loops iterate over days i and cities j, and the innermost loop iterates over potential previous cities h.

   for i in range(1, k + 1):
       for j in range(n):
           for h in range(n):
               f[i][j] = max(
                   f[i][j],
                   f[i - 1][h] + (stayScore[i - 1][j] if j == h else travelScore[h][j]),
               )

3. Decision Points:

   • If the tourist decides to stay in city j, they accumulate stayScore[i-1][j] on top of what they had on day i-1.
   • If the tourist travels from city h to city j, they earn travelScore[h][j] in addition to the score from day i-1.

4. Final Solution:

   • After populating the DP table, the result is the maximum score obtainable on day k across all cities, given by max(f[k]).

   return max(f[k])

This approach thoroughly evaluates all possibilities of staying or traveling across the cities for each day, thus ensuring the calculated score is indeed the maximum achievable over the specified duration. This use of dynamic programming allows us to handle the complexity efficiently across the various combinations of city itineraries.

Example Walkthrough

Let's work through a small example to illustrate the solution approach. Suppose we have 3 cities (n = 3) and the journey lasts 2 days (k = 2). The stayScore and travelScore arrays are given as follows:

• stayScore = [[5, 6, 3], [2, 8, 7]]
• travelScore = [[0, 2, 1], [4, 0, 3], [2, 2, 0]]

Day 0 (Initialization):

• Initialize a DP table f with dimensions (k + 1) x n, filled with -inf.
• Set f[0][j] = 0 for all cities j since the tourist starts with 0 points.

f = [
    [0, 0, 0],   # Day 0
    [-inf, -inf, -inf], # Day 1
    [-inf, -inf, -inf]  # Day 2
]

Day 1:

For each city j, calculate scores considering either staying or coming from another city h.

• City 0:

  • Stay: f[1][0] = f[0][0] + stayScore[0][0] = 0 + 5 = 5
  • From City 1: f[1][0] = max(5, f[0][1] + travelScore[1][0] = 0 + 4) = 5
  • From City 2: f[1][0] = max(5, f[0][2] + travelScore[2][0] = 0 + 2) = 5

• City 1:

  • Stay: f[1][1] = f[0][1] + stayScore[0][1] = 0 + 6 = 6
  • From City 0: f[1][1] = max(6, f[0][0] + travelScore[0][1] = 0 + 2) = 6
  • From City 2: f[1][1] = max(6, f[0][2] + travelScore[2][1] = 0 + 2) = 6

• City 2:

  • Stay: f[1][2] = f[0][2] + stayScore[0][2] = 0 + 3 = 3
  • From City 0: f[1][2] = max(3, f[0][0] + travelScore[0][2] = 0 + 1) = 3
  • From City 1: f[1][2] = max(3, f[0][1] + travelScore[1][2] = 0 + 3) = 3

f = [
    [0, 0, 0], 
    [5, 6, 3], # Calculated scores after day 1
    [-inf, -inf, -inf]
]

Day 2:

Similarly, for each city j, compute potential scores:

• City 0:

  • Stay: f[2][0] = f[1][0] + stayScore[1][0] = 5 + 2 = 7
  • From City 1: f[2][0] = max(7, f[1][1] + travelScore[1][0] = 6 + 4) = 10
  • From City 2: f[2][0] = max(10, f[1][2] + travelScore[2][0] = 3 + 2) = 10

• City 1:

  • Stay: f[2][1] = f[1][1] + stayScore[1][1] = 6 + 8 = 14
  • From City 0: f[2][1] = max(14, f[1][0] + travelScore[0][1] = 5 + 2) = 14
  • From City 2: f[2][1] = max(14, f[1][2] + travelScore[2][1] = 3 + 2) = 14

• City 2:

  • Stay: f[2][2] = f[1][2] + stayScore[1][2] = 3 + 7 = 10
  • From City 0: f[2][2] = max(10, f[1][0] + travelScore[0][2] = 5 + 1) = 10
  • From City 1: f[2][2] = max(10, f[1][1] + travelScore[1][2] = 6 + 3) = 10

f = [
    [0, 0, 0], 
    [5, 6, 3], 
    [10, 14, 10] # Calculated scores after day 2
]

Result:

The maximum score after 2 days is max(f[2]) = 14, which is achieved by staying in or traveling to city 1 on both days to maximize points.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(k * n^2). This is because there are three nested loops: the outer loop runs k times, the middle loop runs n times for each k, and the innermost loop also runs n times for each n. Therefore, the total number of operations is proportional to k * n * n = k * n^2.

The space complexity of the code is O(k * n) because it uses a 2D list f of size (k + 1) * n to store intermediate results. This is the dominant space usage in the algorithm.

Learn more about how to find time and space complexity quickly.