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:
curr during day i, they will earn stayScore[i][curr] points.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 <= 2001 <= k <= 200n == travelScore.length == travelScore[i].length == stayScore[i].lengthk == stayScore.length1 <= stayScore[i][j] <= 1000 <= travelScore[i][j] <= 100travelScore[i][i] == 0Problem Overview: You are given multiple cities and several travel days. Each day you can either stay in your current city to gain stayScore[day][city] or travel to another city to gain travelScore[from][to]. The goal is to plan movements across days to maximize the total points earned.
Approach 1: Brute Force Recursion (Exponential Time)
The most direct idea is to try every possible decision each day: either stay in the same city or travel to another one. A recursive function explores all combinations of city choices for every day. For each state (day, city), the recursion branches into staying or traveling to every other city.
This approach quickly becomes infeasible because the number of paths grows exponentially with the number of days and cities. Time complexity is O(n^k) in the worst case (where n is the number of cities and k is the number of days). Space complexity is O(k) due to recursion depth. This version mainly helps understand the decision structure before introducing dynamic programming.
Approach 2: Dynamic Programming (O(k * n^2))
Dynamic programming eliminates repeated calculations by storing the best score achievable for each state. Define dp[day][city] as the maximum points obtainable after finishing day days while ending in city. For every new day, evaluate two choices: stay in the same city or travel from any other city.
Staying adds stayScore[day][city] to dp[day-1][city]. Traveling checks all possible previous cities prev and updates the score using dp[day-1][prev] + travelScore[prev][city]. The algorithm iterates through days, then cities, and computes the best transition. Because each city considers all previous cities, the time complexity becomes O(k * n^2). The DP table requires O(k * n) space.
This solution naturally models the problem as a layered decision graph across days. Each layer represents cities for that day, and transitions represent travel or staying. The structure closely resembles problems solved with matrix transitions and state updates common in array-based DP.
Approach 3: Space Optimized Dynamic Programming (O(k * n^2), O(n) space)
The DP relation only depends on the previous day. Instead of storing a full k × n table, maintain two arrays: prev and curr. For each day, compute the best score for every city using values from prev, then swap arrays.
This reduces memory usage from O(k * n) to O(n) while preserving the same transition logic. Time complexity remains O(k * n^2) because each city still checks all possible previous cities when considering travel transitions.
Recommended for interviews: The dynamic programming approach is what interviewers expect. Starting with the brute-force recursion shows you understand the decision tree. Converting it into a DP state dp[day][city] demonstrates optimization skills and familiarity with classic multi-stage DP problems.
The problem can be tackled using dynamic programming by keeping a DP table `dp` where `dp[i][j]` represents the maximum points the tourist can earn on the `i`-th day when staying in city `j`. The key is to decide on each day whether to stay in the current city for the maximum 'stayScore' or travel to another city for added 'travelScore'.
This solution constructs a DP table where each entry dp[i][j] depicts the maximum score after the i-th day in city j. The update on day `i` depends on whether the previous day was spent in the same city for stayScore or coming from another city with travelScore. After initializing days, we loop through all cities, updating the dp[i][j] from each other city's dp[i-1][.] thus considering both staying and traveling.
Time Complexity: O(k * n^2) since we iterate over k days and compare scores between every pair of n cities.
Space Complexity: O(k * n) for storing the dp table.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(k * n^2) since we iterate over k days and compare scores between every pair of n cities. Space Complexity: O(k * n) for storing the dp table. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(n^k) | O(k) | Conceptual understanding of all possible city transitions |
| Dynamic Programming (DP Table) | O(k * n^2) | O(k * n) | General optimal solution for maximizing points across days and cities |
| Space Optimized DP | O(k * n^2) | O(n) | Preferred when memory usage matters while keeping the same DP logic |
Leetcode Biweekly Contest 142 | 3332. Maximum Points Tourist Can Earn | Codefod • CodeFod • 370 views views
Watch 3 more video solutions →Practice Maximum Points Tourist Can Earn with our built-in code editor and test cases.
Practice on FleetCode