Maximum Points Tourist Can Earn
MedPrompt
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
currduring dayi, they will earnstayScore[i][curr]points. - Move to another city: If the tourist moves from their current city
currto citydest, they will earntravelScore[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 <= 2001 <= k <= 200n == travelScore.length == travelScore[i].length == stayScore[i].lengthk == stayScore.length1 <= stayScore[i][j] <= 1000 <= travelScore[i][j] <= 100travelScore[i][i] == 0
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible sequence of decisions the tourist can make over the k days. A path is defined by a starting city and the sequence of cities visited. We can use a recursive function to explore all paths, calculate the score for each, and find the maximum.
Algorithm
- Define a recursive function, say
findMaxScore(day, currentCity), that calculates the maximum score obtainable fromdaytok-1, starting incurrentCity. - The base case for the recursion is when
day == k. In this case, the journey is over, so we return 0. - In the recursive step, calculate the scores for the two possible choices:
a. Stay: The score is
stayScore[day][currentCity] + findMaxScore(day + 1, currentCity). b. Move: Iterate through all other citiesdest. The score for moving istravelScore[currentCity][dest] + findMaxScore(day + 1, dest). Take the maximum over alldest. - The function returns
max(stay_score, move_score). - To get the final answer, call
findMaxScore(0, startCity)for every possiblestartCityand return the overall maximum.
Walkthrough
We define a recursive function, say findMaxScore(day, currentCity). This function calculates the maximum score obtainable from day until k-1, given the tourist is in currentCity at the start of day. The base case for the recursion is when day == k, meaning the journey is over, so we return 0. In the recursive step for findMaxScore(day, currentCity), we calculate the score for two choices:
- Stay: The score is
stayScore[day][currentCity] + findMaxScore(day + 1, currentCity). - Move: We iterate through all possible destination cities
dest(wheredest != currentCity). The score for moving todestistravelScore[currentCity][dest] + findMaxScore(day + 1, dest). We take the maximum score among all possible destinations.
The function returns the maximum of the "stay" and "move" scores. The main function will call findMaxScore(0, startCity) for every possible startCity from 0 to n-1 and take the maximum result. This approach is extremely slow because it recomputes the same subproblems multiple times. For example, findMaxScore(day, city) will be called for many different paths that lead to city on day.
// This is a conceptual illustration. It will time out for the given constraints.class Solution { int n; int k; int[][] stayScore; int[][] travelScore; public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) { this.n = n; this.k = k; this.stayScore = stayScore; this.travelScore = travelScore; int maxScore = 0; // The tourist can start in any city. for (int startCity = 0; startCity < n; startCity++) { maxScore = Math.max(maxScore, findMaxScore(0, startCity)); } return maxScore; } private int findMaxScore(int day, int currentCity) { if (day == k) { return 0; } // Option 1: Stay in the current city int stayPoints = stayScore[day][currentCity] + findMaxScore(day + 1, currentCity); // Option 2: Move to another city int movePoints = 0; for (int destCity = 0; destCity < n; destCity++) { if (destCity != currentCity) { movePoints = Math.max(movePoints, travelScore[currentCity][destCity] + findMaxScore(day + 1, destCity)); } } return Math.max(stayPoints, movePoints); }}Complexity
Time
O(n * n^k) For each starting city, the recursive function explores a tree of decisions. The depth of the tree is `k`, and the branching factor at each node is `n` (1 stay choice, `n-1` move choices). This leads to approximately `n^k` paths. Since there are `n` possible starting cities, the total time complexity is `O(n * n^k)`.
Space
O(k) The space complexity is determined by the maximum depth of the recursion stack, which is equal to the number of days, `k`.
Trade-offs
Pros
Simple to understand and implement based on the problem description.
Cons
Extremely inefficient due to re-computation of the same subproblems.
The time complexity makes it infeasible for the given constraints.
A more efficient approach is to use dynamic programming to avoid recomputing results for the same subproblems. We can build a table dp[i][j] to store the maximum score achievable at the beginning of day i, ending in city j.
Algorithm
- Create a 2D DP table,
dp, of size(k+1) x n. dp[i][j]will store the maximum score at the beginning of dayi, being in cityj.- Initialization: Set
dp[0][j] = 0for alljfrom0ton-1, as the tourist can start in any city with an initial score of 0. - Iteration: Loop through days
ifrom0tok-1. - For each day
i, loop through each possible destination cityjfrom0ton-1. - Calculate
dp[i+1][j]using the recurrence relation:dp[i+1][j] = max(dp[i][j] + stayScore[i][j], max_{c != j} (dp[i][c] + travelScore[c][j])). The innermaxis found by iterating through all possible previous citiesc. - Result: After the loops complete, the maximum score is the maximum value in the last row of the DP table,
max(dp[k]).
Walkthrough
We define dp[i][j] as the maximum score accumulated at the beginning of day i, with the tourist being in city j. The DP table will have dimensions (k+1) x n.
Initialization: At the beginning of day 0 (i.e., i=0), the tourist can start in any city with a score of 0. So, we initialize dp[0][j] = 0 for all cities j.
Recurrence Relation: We iterate from day i = 0 to k-1. To compute dp[i+1][j] (max score at the start of day i+1 in city j), we consider all possible cities c the tourist could have been in at the start of day i.
- If the tourist was in city
jand stayed: The score would bedp[i][j] + stayScore[i][j]. - If the tourist was in city
c != jand moved: The score would bedp[i][c] + travelScore[c][j].
The value dp[i+1][j] is the maximum of all these possibilities. This is equivalent to a top-down recursive approach with memoization, which avoids the redundant calculations of the brute-force method.
Final Answer: After filling the table up to dp[k], the maximum score at the end of the journey is the maximum value in the last row of the DP table, i.e., max(dp[k][j]) for all j from 0 to n-1.
class Solution { public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) { long[][] dp = new long[k + 1][n]; // dp[i][j] = max score at the beginning of day i, in city j // Base case: dp[0][j] = 0 for all j, as we can start anywhere with 0 score. for (int i = 0; i < k; i++) { // i is the current day for (int j = 0; j < n; j++) { // j is the destination city for day i // Calculate max score from traveling to city j from any other city c long maxTravelScore = 0; for (int c = 0; c < n; c++) { // c is the city at the start of day i if (c != j) { maxTravelScore = Math.max(maxTravelScore, dp[i][c] + travelScore[c][j]); } } // Calculate score from staying in city j long stayScoreVal = dp[i][j] + stayScore[i][j]; // dp[i+1][j] is the max score at the end of day i (start of day i+1), in city j dp[i + 1][j] = Math.max(stayScoreVal, maxTravelScore); } } long maxTotalScore = 0; for (int j = 0; j < n; j++) { maxTotalScore = Math.max(maxTotalScore, dp[k][j]); } return (int) maxTotalScore; }}Complexity
Time
O(k * n^2) We iterate through `k` days. For each day, we compute `n` new DP states. Each state `dp[i+1][j]` requires an inner loop of size `n` to consider all possible previous cities. This results in a total time complexity of `O(k * n * n)`.
Space
O(k * n) We use a DP table of size `(k+1) x n` to store the maximum scores for each day and city.
Trade-offs
Pros
Guarantees finding the optimal solution.
Significantly more efficient than brute force.
Feasible for the given problem constraints.
Cons
Uses O(k * n) space, which might be large if
kandnare very large.
This approach improves upon the standard dynamic programming solution by reducing the space complexity. We observe that to calculate the scores for the current day, we only need the scores from the previous day.
Algorithm
- Initialize an array
prevDpof sizenwith all zeros. This represents the scores at the beginning of day 0. - Loop through each day
ifrom0tok-1. - Inside the loop, create a new array
currDpof sizento store the scores for the current day. - For each city
jfrom0ton-1: a. Calculate the maximum score if traveling tojfrom any other cityc:maxTravelScore = max_{c != j} (prevDp[c] + travelScore[c][j]). b. Calculate the score if staying inj:stayScoreVal = prevDp[j] + stayScore[i][j]. c. SetcurrDp[j] = max(maxTravelScore, stayScoreVal). - After the inner loop (over
j) finishes, updateprevDp = currDpto prepare for the next day's calculation. - After the outer loop (over
i) finishes, the final maximum score is the largest value in theprevDparray.
Walkthrough
The recurrence relation dp[i+1][j] = max(dp[i][j] + stayScore[i][j], max_{c != j} (dp[i][c] + travelScore[c][j])) shows that the calculation for day i+1 only depends on the results from day i. This means we don't need to store the entire k x n table.
Instead of a 2D table, we can use just two arrays of size n: one to store the scores of the previous day (prevDp) and one for the current day (currDp).
Initialization: prevDp[j] = 0 for all j, representing the scores at the beginning of day 0.
Iteration: We loop from day i = 0 to k-1. In each iteration, we compute currDp based on prevDp using the same logic as the standard DP approach. After computing currDp for all cities, we update prevDp by setting it to currDp for the next day's calculation.
Final Answer: After k iterations, the prevDp array will hold the maximum scores at the end of the journey. The result is the maximum value in this array.
class Solution { public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) { long[] prevDp = new long[n]; // prevDp[j] = max score at the beginning of the current day, in city j // Initially, at day 0, score is 0 for any starting city. for (int i = 0; i < k; i++) { // i is the current day long[] currDp = new long[n]; for (int j = 0; j < n; j++) { // j is the destination city for day i // Calculate max score from traveling to city j long maxTravelScore = 0; for (int c = 0; c < n; c++) { // c is the city at the start of day i if (c != j) { maxTravelScore = Math.max(maxTravelScore, prevDp[c] + travelScore[c][j]); } } // Calculate score from staying in city j long stayScoreVal = prevDp[j] + stayScore[i][j]; // currDp[j] is the max score at the end of day i currDp[j] = Math.max(stayScoreVal, maxTravelScore); } prevDp = currDp; // Prepare for the next day } long maxTotalScore = 0; for (int j = 0; j < n; j++) { maxTotalScore = Math.max(maxTotalScore, prevDp[j]); } return (int) maxTotalScore; }}Complexity
Time
O(k * n^2) The time complexity remains the same as the standard DP approach. The nested loop structure for iterating through days, destination cities, and source cities is unchanged.
Space
O(n) We only need two arrays of size `n` to store the DP states for the previous and current days. Therefore, the space complexity is reduced to `O(n)`.
Trade-offs
Pros
Maintains the same time efficiency as the standard DP approach.
Highly memory efficient, using only O(n) space.
This is the most efficient solution for the given constraints.
Cons
The code can be slightly less intuitive to read compared to the 2D DP table version.
Solutions
Solution
class Solution {public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) { int[][] f = new int[k + 1][n]; for (var g : f) { Arrays.fill(g, Integer.MIN_VALUE); } Arrays.fill(f[0], 0); for (int i = 1; i <= k; ++i) { for (int j = 0; j < n; ++j) { for (int h = 0; h < n; ++h) { f[i][j] = Math.max(f[i][j], f[i - 1][h] + (j == h ? stayScore[i - 1][j] : travelScore[h][j])); } } } return Arrays.stream(f[k]).max().getAsInt(); }}class Solution {public: int maxScore(int n, int k, vector<vector<int>> &stayScore, vector<vector<int>> &travelScore) { int f[k + 1][n]; memset(f, 0xc0, sizeof(f)); memset(f[0], 0, sizeof(f[0])); for (int i = 1; i <= k; ++i) { for (int j = 0; j < n; ++j) { for (int h = 0; h < n; ++h) { f[i][j] = max(f[i][j], f[i - 1][h] + (j == h ? stayScore[i - 1][j] : travelScore[h][j])); } } } return *max_element(f[k], f[k] + n); }};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])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.