Is Maximum Points Tourist Can Earn easy or hard?

Maximum Points Tourist Can Earn is generally considered a medium-level dynamic programming problem. The main challenge is identifying the correct DP state and handling transitions between cities. Once the dp[day][city] definition is clear, the implementation becomes straightforward.

Maximum Points Tourist Can Earn Python/Java solution

Most implementations use a DP table or two rolling arrays. For each day, iterate through all cities and compute the best score by comparing staying in the same city versus traveling from other cities. The same logic works in Python, Java, and C++ with nested loops over days and cities.

How to solve Maximum Points Tourist Can Earn in O(n)?

The full problem cannot be solved in pure O(n) time because each city transition may depend on every other city from the previous day. The best practical solution uses dynamic programming with O(k * n^2) time. However, memory usage can be reduced to O(n) by storing only the previous day's DP values.

What is the best approach for Maximum Points Tourist Can Earn?

Dynamic programming is the most effective approach. Define dp[day][city] as the maximum points achievable after a given day while ending in a specific city. Each state considers staying in the same city or traveling from any other city. This leads to an O(k * n^2) time solution with O(k * n) space.

Is Maximum Points Tourist Can Earn asked at Google/Amazon/Meta?

Dynamic programming problems involving multi-day decisions and transition matrices frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of city travel optimization and stage-based DP are common patterns used to evaluate problem decomposition and state design skills.

What data structure is used in Maximum Points Tourist Can Earn?

The core structure is a dynamic programming table or arrays that store the best score for each (day, city) state. The inputs are typically represented as 2D arrays or matrices for stayScore and travelScore. Iterating through these matrices efficiently is key to implementing the DP transitions.

What is the time complexity of Maximum Points Tourist Can Earn?

The optimal dynamic programming solution runs in O(k * n^2) time, where n is the number of cities and k is the number of days. For each day and destination city, the algorithm checks all possible previous cities to evaluate travel transitions. Space complexity is O(k * n), which can be optimized to O(n).

Description Hints 2 Solution Video 9:17

3332. Maximum Points Tourist Can Earn

Medium47.3% acceptance1 company

You are given two integers, n and k, along with two 2D integer arrays, stayScore and travelScore.

A tourist is visiting a country with n cities, where each city is directly connected to every other city. The tourist's journey consists of exactly k 0-indexed days, and they can choose any city as their starting point.

Each day, the tourist has two choices:

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

Return the maximum possible points the tourist can earn.

Example 1:

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

Output: 3

Explanation:

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

Explanation:

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

Asked at 1 company

D. E. Shaw

Topics

Hints open one at a time

Hint 1

Use DP.

Hint 2

dp[i][j] is the maximum score that you can achieve in your last i actions by starting from city j.

9:17

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

2
1
[[2,3]]
[[0,2],[1,0]]

Input

3
2
[[3,4,2],[2,1,2]]
[[0,2,1],[2,0,4],[3,2,0]]

Your code is saved on this device.Solution