#3332

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Points Tourist Can Earn

Calculate the maximum points a tourist can earn by choosing optimal city moves over k days using state transition DP.

Problem Statement

A tourist plans to visit n cities over exactly k days. Each day, they can either stay in their current city to earn stayScore or travel to another city to earn travelScore. The tourist can start in any city, and the goal is to maximize total points across all days.

You are given two 2D arrays, stayScore and travelScore, representing points earned for staying or traveling. Compute the maximum points achievable following the rules, considering all possible city sequences and transitions while applying state transition dynamic programming.

Examples

Example 1

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

Output: 3

The tourist earns the maximum number of points by starting in city 1 and staying in that city.

Example 2

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

Output: 8

The tourist earns the maximum number of points by starting in city 1, staying in that city on day 0, and traveling to city 2 on day 1.

Constraints

1 <= n <= 200
1 <= k <= 200
n == travelScore.length == travelScore[i].length == stayScore[i].length
k == stayScore.length
1 <= stayScore[i][j] <= 100
0 <= travelScore[i][j] <= 100
travelScore[i][i] == 0

Solution Approach

Initialize DP Table

Create a 2D DP table dp[day][city] where each entry represents the maximum points achievable ending in that city on that day. Initialize the first day with stayScore[0][city] since the tourist can start in any city.

Iterate with State Transitions

For each subsequent day, update dp[day][city] by considering staying in the same city or traveling from any other city. For each city i, compute dp[day][i] = max(dp[day-1][j] + (i==j?stayScore[day][i]:travelScore[j][i] + stayScore[day][i])) to capture the optimal transition.

Compute Maximum Points

After filling the DP table for all k days, the answer is the maximum value in the last row of dp, representing the highest points achievable across any ending city.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(k * n^2) due to iterating through each day and considering transitions from all cities. Space complexity is O(k * n) for the DP table, which can be optimized to O(n) using rolling arrays.

What Interviewers Usually Probe

Look for clear initialization of the DP table for the first day.
Expect candidate to handle both staying and traveling transitions explicitly.
Check if the solution considers starting from any city and updates maximum correctly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include the stayScore when traveling to a new city.
Incorrectly initializing the DP table, especially for the first day.
Assuming a fixed starting city instead of considering all possible starting cities.

Follow-up variants

Modify points calculation to include negative travel penalties.
Limit the number of allowed city travels per day instead of unlimited travel.
Extend to weighted paths between cities affecting both travelScore and stayScore.

FAQ

What is the main pattern used in Maximum Points Tourist Can Earn?

The problem uses state transition dynamic programming to track maximum points for each city over each day.

How do I start solving the problem?

Initialize a DP table for day 0 using stayScore and iterate each day considering all possible stay or travel transitions.

Can space be optimized?

Yes, instead of a full k x n table, use a rolling array to reduce space from O(k*n) to O(n).

What are common mistakes to avoid?

Common mistakes include missing stayScore during transitions, wrong initialization, or assuming a fixed starting city.

How does traveling impact points?

Traveling from city j to city i adds travelScore[j][i] plus stayScore[i] for that day; ignoring this leads to incorrect totals.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxScore(
        self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]
    ) -> int:
        f = [[-inf] * n for _ in range(k + 1)]
        f[0] = [0] * n
        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]),
                    )
        return max(f[k])

Continue Practicing

#3363 find the maximum number of fruits collected #3276 select cells in grid with maximum score #3393 count paths with the given xor value