LeetCode 3332: Maximum Points Tourist Can Earn Solution
Master LeetCode problem 3332 (Maximum Points Tourist Can Earn), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
3332. Maximum Points Tourist Can Earn
Problem Explanation
Explanation:
To solve this problem, we can use dynamic programming. We will maintain a 2D array, dp, where dp[i][j] represents the maximum points the tourist can earn after i days when starting from city j. At each day, the tourist can either stay in the current city or move to another city, so we need to consider both options.
We will iterate over each day and each city to update the dp array by considering the maximum points the tourist can earn by staying or moving to another city. Finally, we return the maximum points the tourist can earn after k days starting from any city.
Algorithm:
- Initialize a 2D array, dp, of size (k + 1) x n, filled with zeros.
- Iterate over each day from 0 to k and each city from 0 to n-1.
- For each day and city, update dp[i][j] as the maximum of:
- dp[i][j] + stayScore[i][j] (if staying in the current city)
- dp[i-1][k] + travelScore[k][j] for all k from 0 to n-1 (if moving to another city)
- Return the maximum value in the last row of dp.
Time Complexity: O(n^2 * k) where n is the number of cities and k is the number of days. Space Complexity: O(n * k) for the dp array.
:
Solution Code
class Solution {
public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) {
int[][] dp = new int[k + 1][n];
for (int i = 1; i <= k; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i-1][j] + stayScore[i-1][j];
for (int k = 0; k < n; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + travelScore[k][j]);
}
}
}
int maxPoints = 0;
for (int i = 0; i < n; i++) {
maxPoints = Math.max(maxPoints, dp[k][i]);
}
return maxPoints;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 3332 (Maximum Points Tourist Can Earn)?
This page provides optimized solutions for LeetCode problem 3332 (Maximum Points Tourist Can Earn) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 3332 (Maximum Points Tourist Can Earn)?
The time complexity for LeetCode 3332 (Maximum Points Tourist Can Earn) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 3332 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3332 in Java, C++, or Python.