We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Points Tourist Can Earn

Number: 3587

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

A tourist is visiting a country with n cities where every pair of different cities is directly connected. The journey lasts exactly k days (indexed from 0). At the start, the tourist can choose any city. On each day i the tourist can either: • Stay in the current city and earn stayScore[i][curr]. • Travel to another city (must be a different city) and earn travelScore[curr][dest]. Return the maximum total points the tourist can earn over the k days.

Key Insights

  • Use dynamic programming where dp[i][city] represents the maximum points attainable up to day i ending in that city.
  • For day 0, because any starting city is allowed, consider both the case where the tourist stays in the chosen starting city (earning stayScore[0][city]) and the case where the tourist starts in one city and immediately travels to another city (earning travelScore[start][city]).
  • For subsequent days, use the previous day’s dp values to compute:
    • If staying in the same city, add the corresponding stayScore for that day.
    • If traveling, add the travelScore from the previous city to the destination.
  • The answer will be the maximum value among all dp[k-1][city] after processing k days.

Space and Time Complexity

Time Complexity: O(k * n^2)
Space Complexity: O(n) if optimized by reusing just the previous day’s dp array, or O(k * n) if a full 2D dp table is maintained.

Solution

We solve the problem using dynamic programming.

  1. Define dp[i][city] as the maximum points attainable by end of day i if the tourist is in city.
  2. For day 0, initialize dp[0][city] as the maximum between (a) staying in that city (score = stayScore[0][city]) and (b) coming from another city by traveling (score = max{travelScore[prev][city] for all prev != city}).
  3. For every subsequent day i (from 1 to k-1), update dp[i][dest] by checking every possible previous city:
    • If staying (prev == dest), score = dp[i-1][dest] + stayScore[i][dest].
    • If traveling (prev != dest), score = dp[i-1][prev] + travelScore[prev][dest].
      Then take the maximum of these over all possible previous cities.
  4. Finally, the answer is the maximum value in dp[k-1] across all cities.

The key trick is to correctly initialize day 0 to account for both possibilities since the starting city is freely chosen.

Code Solutions

# Python Solution

def maxPoints(n, k, stayScore, travelScore):
    # Initialize dp for day 0
    dp = [-10**9] * n  # Large negative value for initialization
    # For each city, consider starting by staying in the city or traveling from another city
    for city in range(n):
        # Option 1: Staying in the city as the start
        option_stay = stayScore[0][city]
        # Option 2: Traveling from some other city (if any)
        option_travel = 0
        for prev in range(n):
            if prev != city:
                option_travel = max(option_travel, travelScore[prev][city])
        dp[city] = max(option_stay, option_travel)
    
    # Process days 1 to k-1
    for day in range(1, k):
        new_dp = [-10**9] * n
        for dest in range(n):
            # For each possible previous city compute the best route to dest
            for prev in range(n):
                if prev == dest:
                    # Stay in the same city: add the stay score on current day
                    candidate = dp[prev] + stayScore[day][dest]
                else:
                    # Travel from prev city to dest city: add travel score
                    candidate = dp[prev] + travelScore[prev][dest]
                new_dp[dest] = max(new_dp[dest], candidate)
        dp = new_dp  # Move to next day
    # Maximum points achievable after k days
    return max(dp)

# Example usage:
n = 3
k = 2
stayScore = [[3,4,2],[2,1,2]]
travelScore = [[0,2,1],[2,0,4],[3,2,0]]
print(maxPoints(n, k, stayScore, travelScore))  # Expected output: 8
← Back to All Questions