LeetCode 3332: Maximum Points Tourist Can Earn

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:

1. Initialize a 2D array, dp, of size (k + 1) x n, filled with zeros.
2. Iterate over each day from 0 to k and each city from 0 to n-1.
3. 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)
4. 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.

:

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;
    }
}