LeetCode 3332 - Maximum Points Tourist Can Earn

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem asks us to maximize the points a tourist can earn over a fixed number of days, k, while visiting n cities. Each day, the tourist has a choice: either stay in the current city and earn points according to stayScore for that day and city, or travel to another city and earn points according to travelScore for that move. Importantly, the tourist can start in any city on day 0, and every city is directly connected to every other city, so travel is always possible.

The input consists of:

An integer n representing the number of cities.
An integer k representing the number of days.
A 2D list stayScore of size k x n where stayScore[i][j] is the points earned if staying in city j on day i.
A 2D list travelScore of size n x n where travelScore[i][j] is the points earned when traveling from city i to city j. Diagonal entries are zero because traveling from a city to itself is not allowed.

The output is a single integer representing the maximum points achievable over k days.

Key constraints include 1 <= n, k <= 200 and 0 <= travelScore[i][j] <= 100. The upper limit of 200 for both n and k rules out naive recursive or brute-force solutions that explore every possible sequence of moves, as the total number of sequences grows exponentially.

Important edge cases include:

Only one day (k=1), where the tourist should simply choose the city with the highest stayScore.
Only one city (n=1), which forces the tourist to stay in the same city every day.
Maximum size inputs to test performance limits.
Travel scores where traveling might sometimes be worse than staying, which tests whether the algorithm correctly chooses between stay and move.

Approaches

The brute-force approach would attempt to explore all possible sequences of cities over k days. For each day, it would consider staying in the current city or moving to any other city. While this guarantees the correct answer, the time complexity is O(n^k), which is clearly infeasible for n, k up to 200.

The key observation for a more efficient solution is that the problem has optimal substructure and overlapping subproblems, making it suitable for dynamic programming. For each day i and city j, we only need to know the maximum score achievable up to day i-1 in any city, and then we can calculate the score for day i in city j by either staying or traveling. This reduces the complexity to O(k * n^2), which is manageable for n, k ≤ 200.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^k)	O(k)	Explore all sequences of stay/move decisions
Dynamic Programming	O(k * n^2)	O(n)	Compute max score for each day and city using previous day's results

Algorithm Walkthrough

Initialize a DP array dp of size n to store the maximum score for each city on the current day. Initially, set dp[j] to stayScore[0][j] for day 0 because the tourist can start in any city.
Iterate over each day i from 1 to k-1. For each city j (destination city for day i), calculate the maximum points achievable by either staying or traveling:

a. Staying: Add stayScore[i][j] to dp[j] from the previous day.

b. Traveling: Consider every other city m as the source city from the previous day. Add dp[m] + travelScore[m][j] + stayScore[i][j] and keep track of the maximum. 3. Update the dp array with the newly calculated scores for day i. 4. After processing all k days, the maximum value in dp will be the answer because it represents the best score achievable ending in any city on the last day.

Why it works: By storing the best achievable score for each city for the previous day, we ensure that for each day, we only compute the best possible outcome using optimal substructure. The algorithm always picks the maximum achievable score at each step, ensuring global optimality.

Python Solution

from typing import List

class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        dp = stayScore[0][:]  # Maximum points for each city on day 0

        for day in range(1, k):
            new_dp = [0] * n
            for dest in range(n):
                max_score = 0
                for src in range(n):
                    score = dp[src] + (travelScore[src][dest] if src != dest else 0)
                    max_score = max(max_score, score)
                new_dp[dest] = max_score + stayScore[day][dest]
            dp = new_dp

        return max(dp)

In this implementation, dp represents the maximum score for each city on the current day. For each day, we calculate the maximum score for reaching each city by considering all possible source cities from the previous day, adding the travel score if moving, and then adding the stay score for that day.

Go Solution

func maxScore(n int, k int, stayScore [][]int, travelScore [][]int) int {
    dp := make([]int, n)
    copy(dp, stayScore[0])

    for day := 1; day < k; day++ {
        newDP := make([]int, n)
        for dest := 0; dest < n; dest++ {
            maxScore := 0
            for src := 0; src < n; src++ {
                score := dp[src]
                if src != dest {
                    score += travelScore[src][dest]
                }
                if score > maxScore {
                    maxScore = score
                }
            }
            newDP[dest] = maxScore + stayScore[day][dest]
        }
        dp = newDP
    }

    result := 0
    for _, val := range dp {
        if val > result {
            result = val
        }
    }
    return result
}

The Go implementation follows the same logic as Python. Arrays are used instead of lists, and a temporary newDP slice stores the updated scores for each day.

Worked Examples

Example 1:

n = 2, k = 1
stayScore = [[2, 3]]
travelScore = [[0, 2], [1, 0]]

Day 0: dp = [2, 3]

Maximum score = max(2, 3) = 3

Example 2:

n = 3, k = 2
stayScore = [[3, 4, 2], [2, 1, 2]]
travelScore = [[0, 2, 1], [2, 0, 4], [3, 2, 0]]

Day 0: dp = [3, 4, 2]

Day 1 calculations:

Destination 0: max(3+0, 4+2, 2+3) + 2 = max(3,6,5)+2=6+2=8
Destination 1: max(3+2,4+0,2+2)+1=max(5,4,4)+1=5+1=6
Destination 2: max(3+1,4+4,2+0)+2=max(4,8,2)+2=8+2=10

dp = [8,6,10], maximum = 10

Wait, the problem output is 8 in the example. This indicates that the tourist chooses starting city 1, stays, then moves optimally.

Let's trace carefully:

Day 0 dp = [3,4,2]
Day 1:

Destination 0:

from 0: 3+0 + stayScore[1][0]=3+0+2=5
from 1: 4+2 +2=6+2=8 ??? Wait stayScore added separately

Better: max(dp[src] + travelScore[src][dest] + stayScore[1][dest])

dest=0:

src=0: 3 + 0 + 2=5
src=1: 4 + 2 + 2=8
src=2: 2 +3 +2=7

dest=0 max=8

dest=1:

src=0:3+2+1=6
src=1:4+0+1=5
src=2:2+2+1=5

dest=1 max=6

dest=2:

src=0:3+1+2=6
src=1:4+4+2=10
src=2:2+0+2=4

dest=2 max=10

Wait, problem says output=8, so the correct path is staying in city 1 day 0, then moving to city 2 day 1?