Problem Description

You have a tourist visiting a country with n cities, where every city is directly connected to every other city. The tourist will spend exactly k days (indexed from 0 to k-1) traveling and can start their journey from any city.

On each day i, the tourist has two options:

• Stay in the current city: If they remain in city curr on day i, they earn stayScore[i][curr] points
• Travel to a different city: If they move from city curr to city dest, they earn travelScore[curr][dest] points

The goal is to find the maximum total points the tourist can earn over the entire k-day journey.

The solution uses dynamic programming where f[i][j] represents the maximum points that can be earned by day i when ending at city j. The state transition considers both staying in the same city (when h == j) and traveling from a different city h to city j. The answer is the maximum value among all cities on day k.

The key insight is that for each day and each possible destination city, we need to consider all possible previous cities the tourist could have been in, choosing the option that maximizes the total score.

Intuition

The problem asks us to find the optimal sequence of decisions over k days to maximize points. This is a classic dynamic programming scenario because:

1. Optimal substructure: The best solution for k days depends on the best solutions for k-1 days. If we know the maximum points we can achieve by day i-1 ending at each city, we can determine the maximum points for day i.

2. Overlapping subproblems: Multiple paths can lead to the same city on the same day, and we only care about the one with maximum points.

The key insight is to track the state as "what's the maximum score I can achieve by day i if I end up in city j?" This naturally leads to the DP formulation f[i][j] = maximum points achievable by day i ending at city j.

For each new day i and each possible destination city j, we need to consider all possibilities:

• We could have been in city j already (stayed) and earned stayScore[i-1][j]
• We could have been in any other city h and traveled to j, earning travelScore[h][j]

Since we want to maximize points, we try all possible previous cities h and take the maximum. The recurrence becomes: f[i][j] = max(f[i-1][h] + score) where score is either stayScore[i-1][j] if h == j or travelScore[h][j] if h != j.

Starting with f[0][j] = 0 for all cities (day 0, no points earned yet), we build up the solution day by day. The final answer is the maximum value among all cities on day k, since the tourist can end their journey in any city.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a bottom-up dynamic programming approach using a 2D table to track the maximum scores.

Data Structure:

• f[i][j]: A 2D array where f[i][j] represents the maximum points achievable by day i when ending at city j
• Initialize all values to negative infinity (-inf) except for day 0, which is set to 0 for all cities

Implementation Steps:

1. Initialization: Create a (k+1) × n DP table where:

   • f[0][j] = 0 for all cities j (starting condition - no points earned on day 0)
   • All other entries are -inf to ensure they get updated with valid scores

2. State Transition: For each day i from 1 to k:

   • For each possible destination city j:
     • For each possible previous city h:
       • Calculate the score based on whether the tourist stayed or traveled:
         • If j == h (stayed): add stayScore[i-1][j] to f[i-1][h]
         • If j != h (traveled): add travelScore[h][j] to f[i-1][h]
       • Update f[i][j] with the maximum value found

3. Final Answer: Return max(f[k]) - the maximum score among all possible ending cities on day k

Time Complexity: O(k × n²) - we iterate through k days, and for each day, we consider all n² city pairs (from city h to city j)

Space Complexity: O(k × n) for the DP table

The algorithm systematically builds up the solution by considering all possible paths through the cities over k days, ensuring we find the globally optimal solution.

Example Walkthrough

Let's walk through a small example with n = 3 cities and k = 2 days.

Given:

• stayScore = [[1, 3, 2], [2, 1, 4]] (day 0 and day 1 stay scores)
• travelScore = [[0, 2, 1], [3, 0, 2], [1, 4, 0]] (travel scores between cities)

Step 1: Initialize DP Table Create f[3][3] table (k+1 = 3 rows, n = 3 columns):

Day 0: f[0] = [0, 0, 0]  // Starting condition
Day 1: f[1] = [-∞, -∞, -∞]
Day 2: f[2] = [-∞, -∞, -∞]

Step 2: Calculate Day 1 For each destination city j, consider all possible previous cities h:

For city 0 (j=0):

• From city 0 (h=0): stayed → f[0][0] + stayScore[0][0] = 0 + 1 = 1
• From city 1 (h=1): traveled → f[0][1] + travelScore[1][0] = 0 + 3 = 3
• From city 2 (h=2): traveled → f[0][2] + travelScore[2][0] = 0 + 1 = 1
• f[1][0] = max(1, 3, 1) = 3

For city 1 (j=1):

• From city 0 (h=0): traveled → f[0][0] + travelScore[0][1] = 0 + 2 = 2
• From city 1 (h=1): stayed → f[0][1] + stayScore[0][1] = 0 + 3 = 3
• From city 2 (h=2): traveled → f[0][2] + travelScore[2][1] = 0 + 4 = 4
• f[1][1] = max(2, 3, 4) = 4

For city 2 (j=2):

• From city 0 (h=0): traveled → f[0][0] + travelScore[0][2] = 0 + 1 = 1
• From city 1 (h=1): traveled → f[0][1] + travelScore[1][2] = 0 + 2 = 2
• From city 2 (h=2): stayed → f[0][2] + stayScore[0][2] = 0 + 2 = 2
• f[1][2] = max(1, 2, 2) = 2

After Day 1: f[1] = [3, 4, 2]

Step 3: Calculate Day 2 For city 0 (j=0):

• From city 0: stayed → f[1][0] + stayScore[1][0] = 3 + 2 = 5
• From city 1: traveled → f[1][1] + travelScore[1][0] = 4 + 3 = 7
• From city 2: traveled → f[1][2] + travelScore[2][0] = 2 + 1 = 3
• f[2][0] = max(5, 7, 3) = 7

For city 1 (j=1):

• From city 0: traveled → f[1][0] + travelScore[0][1] = 3 + 2 = 5
• From city 1: stayed → f[1][1] + stayScore[1][1] = 4 + 1 = 5
• From city 2: traveled → f[1][2] + travelScore[2][1] = 2 + 4 = 6
• f[2][1] = max(5, 5, 6) = 6

For city 2 (j=2):

• From city 0: traveled → f[1][0] + travelScore[0][2] = 3 + 1 = 4
• From city 1: traveled → f[1][1] + travelScore[1][2] = 4 + 2 = 6
• From city 2: stayed → f[1][2] + stayScore[1][2] = 2 + 4 = 6
• f[2][2] = max(4, 6, 6) = 6

After Day 2: f[2] = [7, 6, 6]

Step 4: Find Maximum The answer is max(f[2]) = max(7, 6, 6) = 7

The optimal path: Start in city 1 → Stay in city 1 on day 0 (earn 3) → Travel to city 0 on day 1 (earn 4) → Total: 7 points.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k * n^2)

The algorithm uses three nested loops:

• The outermost loop iterates k times (from 1 to k)
• The middle loop iterates n times (for each city j)
• The innermost loop iterates n times (for each previous city h)

For each iteration of these three loops, we perform constant time operations (max comparison and array lookups). Therefore, the total time complexity is O(k * n * n) = O(k * n^2).

Space Complexity: O(k * n)

The space complexity is determined by:

• The 2D DP table f with dimensions (k+1) × n, which requires O((k+1) * n) = O(k * n) space
• A few scalar variables (i, j, h) which require O(1) space

Therefore, the total space complexity is O(k * n).

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

Common Pitfalls

1. Incorrect Index Mapping for Score Arrays

The most common mistake is misunderstanding how the day indices map to the score arrays. Since days are indexed from 0 to k-1, but the DP table uses indices from 0 to k (where day 0 is the initialization day with no actions), there's an off-by-one relationship:

• On day i in the DP table (where i ≥ 1), we're actually taking actions for day i-1 in the problem
• Therefore, we should use stayScore[i-1] and travelScore when computing dp[i]

Incorrect Implementation:

# Wrong: Using day index directly
score = dp[day - 1][previous_city] + stayScore[day][current_city]  # Index out of bounds!

Correct Implementation:

# Correct: Adjusting for 0-indexed score arrays
score = dp[day - 1][previous_city] + stayScore[day - 1][current_city]

2. Space Optimization Pitfall

While it's tempting to optimize space by using only two 1D arrays (previous day and current day), be careful not to overwrite values that are still needed:

Problematic Space-Optimized Version:

# This can lead to bugs if not careful about copying
prev = [0] * n
curr = [float('-inf')] * n

for day in range(1, k + 1):
    for current_city in range(n):
        for previous_city in range(n):
            # ... calculate score ...
            curr[current_city] = max(curr[current_city], score)
    prev = curr  # Wrong! This creates a reference, not a copy
    curr = [float('-inf')] * n  # Need to reset for next iteration

Correct Space-Optimized Version:

prev = [0] * n
for day in range(1, k + 1):
    curr = [float('-inf')] * n
    for current_city in range(n):
        for previous_city in range(n):
            if current_city == previous_city:
                score = prev[previous_city] + stayScore[day - 1][current_city]
            else:
                score = prev[previous_city] + travelScore[previous_city][current_city]
            curr[current_city] = max(curr[current_city], score)
    prev = curr  # Now prev points to the completed curr array

3. Initialization Error

Forgetting to properly initialize the DP table can lead to incorrect results. The base case must allow the tourist to start from any city:

Wrong Initialization:

dp = [[0] * n for _ in range(k + 1)]  # Wrong! Non-reachable states should be -inf
dp[0][0] = 0  # Wrong! Tourist can start from any city

Correct Initialization:

dp = [[float('-inf')] * n for _ in range(k + 1)]
dp[0] = [0] * n  # Tourist can start from any city with 0 initial score