Maximum Points Tourist Can Earn — Problem & Solution
Maximum Points Tourist Can Earn solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Points Tourist Can Earn is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tourist visits a country of n cities, every pair of which is connected by a direct road, for exactly k days (numbered from 0). The tourist may start in any city.
Each day, the tourist in city curr chooses one of two things:
- Stay in
currand earnstayScore[i][curr]points on dayi, or - Move to another city
destand earntravelScore[curr][dest]points.
Return the maximum total number of points the tourist can earn.
Example 1
Input: n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]
Output: 3
Explanation: Start in city 1 and stay there for the day.
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: Start in city 1, stay on day 0 (4 points) and move to city 2 on day 1 (4 points).
Example 3
Input: n = 1, k = 3, stayScore = [[5],[1],[7]], travelScore = [[0]]
Output: 13
Explanation: With one city the tourist stays every day: 5 + 1 + 7.
Constraints
1 <= n <= 2001 <= k <= 200n == travelScore.length == travelScore[i].length == stayScore[i].lengthk == stayScore.length1 <= stayScore[i][j] <= 1000 <= travelScore[i][j] <= 100travelScore[i][i] == 0
Hints for Maximum Points Tourist Can Earn
Hint 1
What matters at the end of a day is only which city the tourist is in — not how they got there.
Hint 2
Let
dp[c]be the best total so far ending the day in cityc. Before day 0 every city is a free starting point, sodp[c] = 0.Hint 3
On day
i,new[c] = max(dp[c] + stayScore[i][c], max over p != c of dp[p] + travelScore[p][c]).
How to solve Maximum Points Tourist Can Earn
Each day's choice depends only on the current city, so a DP over (day, city) captures every itinerary: the tourist ends day i in city c either by staying there or by moving in from another city.
Approach
- Set
dp[c] = 0for every city (the tourist may start anywhere). - For each day
i, computenew[c] = max(dp[c] + stayScore[i][c], max_{p != c} dp[p] + travelScore[p][c]). - Replace
dpwithnew; afterkdays returnmax(dp).
Why it works
The points earned on later days depend only on where the tourist is, so among all histories that end day i in city c, only the best total can lead to an optimal answer. The two cases (stay, move from some p) are exactly the ways to end a day in c.
Complexity
- Time —
O(k · n^2) - Space —
O(n)
Pitfalls
- Staying in
cearnsstayScore, nottravelScore[c][c](which is 0) — keep the move case top != c. - The start city is free — no points are earned just for starting there.
Reference solution
Python
from typing import List
def maxScore(n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
dp = [0] * n
for day in range(k):
stay = stayScore[day]
nd = [0] * n
for c in range(n):
best = dp[c] + stay[c]
for p in range(n):
if p != c:
v = dp[p] + travelScore[p][c]
if v > best:
best = v
nd[c] = best
dp = nd
return max(dp)Java
public static int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
int[] dp = new int[n];
for (int day = 0; day < k; day++) {
int[] nd = new int[n];
for (int c = 0; c < n; c++) {
int best = dp[c] + stayScore[day][c];
for (int p = 0; p < n; p++) {
if (p != c) best = Math.max(best, dp[p] + travelScore[p][c]);
}
nd[c] = best;
}
dp = nd;
}
int ans = 0;
for (int v : dp) ans = Math.max(ans, v);
return ans;
}C++
int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
vector<int> dp(n, 0);
for (int day = 0; day < k; day++) {
vector<int> nd(n, 0);
for (int c = 0; c < n; c++) {
int best = dp[c] + stayScore[day][c];
for (int p = 0; p < n; p++) {
if (p != c) best = max(best, dp[p] + travelScore[p][c]);
}
nd[c] = best;
}
dp = nd;
}
return *max_element(dp.begin(), dp.end());
}JavaScript
var maxScore = function(n, k, stayScore, travelScore) {
var dp = new Array(n).fill(0);
for (var day = 0; day < k; day++) {
var nd = new Array(n).fill(0);
for (var c = 0; c < n; c++) {
var best = dp[c] + stayScore[day][c];
for (var p = 0; p < n; p++) {
if (p !== c && dp[p] + travelScore[p][c] > best) best = dp[p] + travelScore[p][c];
}
nd[c] = best;
}
dp = nd;
}
var ans = 0;
for (var i = 0; i < n; i++) if (dp[i] > ans) ans = dp[i];
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming