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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Points Tourist Can Earn

Difficulty: Medium

Problem Description

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 days, and they can choose any city as their starting point. Each day, the tourist has two choices: stay in their current city and earn stayScore points or move to another city and earn travelScore points. Return the maximum possible points the tourist can earn.

Key Insights

  • The tourist can either stay in the same city or travel to another city every day.
  • The problem can be approached using dynamic programming to keep track of the maximum points earned at each city on each day.
  • Transition between states involves either staying in the same city or moving to another city.

Space and Time Complexity

Time Complexity: O(n * k * n)
Space Complexity: O(n * k)

Solution

This problem can be solved using dynamic programming. We will maintain a 2D array dp where dp[i][j] represents the maximum points earned after i days when ending the day at city j. We will iterate through each day and calculate the maximum points for staying in the same city or moving to another city based on the previous day's points. At the end of k days, the maximum value in the last row of the dp array will be the answer.

Code Solutions

def maxPoints(n, k, stayScore, travelScore):
    dp = [[0] * n for _ in range(k + 1)]
    
    # Initialize the first day's scores
    for j in range(n):
        dp[0][j] = stayScore[0][j]

    for day in range(1, k + 1):
        for curr in range(n):
            # Stay in the same city
            dp[day][curr] = dp[day - 1][curr] + stayScore[day][curr]
            # Move to another city
            for dest in range(n):
                if dest != curr:
                    dp[day][curr] = max(dp[day][curr], dp[day - 1][dest] + travelScore[dest][curr])

    return max(dp[k])
← Back to All Questions