3332. Maximum Points Tourist Can Earn LeetCode Solution
In this guide, you will get 3332. Maximum Points Tourist Can Earn LeetCode Solution with the best time and space complexity. The solution to Maximum Points Tourist Can Earn problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Points Tourist Can Earn
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.
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
Complexity Analysis
Time Complexity: O(n^2k)
Space Complexity: O(nk)
3332. Maximum Points Tourist Can Earn LeetCode Solution in C++
class Solution {
public:
int maxScore(int n, int k, vector<vector<int>>& stayScore,
vector<vector<int>>& travelScore) {
// dp[i][j] := the maximum score after i days being at city j
vector<vector<int>> dp(k + 1, vector<int>(n));
for (int i = 1; i <= k; ++i)
for (int dest = 0; dest < n; ++dest) {
// 1. Stay at the current city.
dp[i][dest] = dp[i - 1][dest] + stayScore[i - 1][dest];
// 2. Travel from any other city.
for (int curr = 0; curr < n; ++curr)
if (curr != dest)
dp[i][dest] =
max(dp[i][dest], dp[i - 1][curr] + travelScore[curr][dest]);
}
return ranges::max(dp[k]);
}
}; /* code provided by PROGIEZ */
3332. Maximum Points Tourist Can Earn LeetCode Solution in Java
class Solution {
public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
// dp[i][j] := the maximum score after i days being at city j
int[][] dp = new int[k + 1][n];
for (int i = 1; i <= k; ++i) {
for (int dest = 0; dest < n; ++dest) {
// 1. Stay at the current city.
dp[i][dest] = dp[i - 1][dest] + stayScore[i - 1][dest];
// 2. Travel from any other city.
for (int curr = 0; curr < n; ++curr)
if (curr != dest)
dp[i][dest] = Math.max(dp[i][dest], dp[i - 1][curr] + travelScore[curr][dest]);
}
}
return Arrays.stream(dp[k]).max().getAsInt();
}
} // code provided by PROGIEZ
3332. Maximum Points Tourist Can Earn LeetCode Solution in Python
class Solution:
def maxScore(
self,
n: int,
k: int,
stayScore: list[list[int]],
travelScore: list[list[int]]
) -> int:
# dp[i][j] := the maximum score after i days being at city j
dp = [[0] * n for _ in range(k + 1)]
for i in range(1, k + 1):
for dest in range(n):
# 1. Stay at the current city.
dp[i][dest] = dp[i - 1][dest] + stayScore[i - 1][dest]
# 2. Travel from any other city.
for curr in range(n):
if curr != dest:
dp[i][dest] = max(dp[i][dest],
dp[i - 1][curr] + travelScore[curr][dest])
return max(dp[k]) # code by PROGIEZ
