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] == 0The 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.
C++
Java
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.
L2. Maximum Points You Can Obtain from Cards | 2 Pointers and Sliding Window Playlist • take U forward • 159,010 views views
Watch 9 more video solutions →Practice Maximum Points Tourist Can Earn with our built-in code editor and test cases.
Practice on FleetCode