Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3587. Maximum Points Tourist Can Earn

My accepted Python solution to LeetCode problem 3587, Maximum Points Tourist Can Earn, running in 7578ms.

  • Difficulty: Medium
  • Python
  • Runtime 7578ms
  • Memory 21.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 7578ms, memory 21.5MB, accepted 2025-12-31.

python
class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        # dp[day][city] = max points that can be earned being at city on day
        # Initialize: on day 0, tourist can start at any city
        dp = [[0] * n for _ in range(k + 1)]
        
        # For day 0, no points earned yet
        for day in range(1, k + 1):
            for curr_city in range(n):
                # Option 1: Stay in current city (came from same city yesterday)
                stay_points = dp[day - 1][curr_city] + stayScore[day - 1][curr_city]
                
                # Option 2: Traveled from another city
                max_travel = 0
                for prev_city in range(n):
                    if prev_city != curr_city:
                        travel_points = dp[day - 1][prev_city] + travelScore[prev_city][curr_city]
                        max_travel = max(max_travel, travel_points)
                
                dp[day][curr_city] = max(stay_points, max_travel)
        
        return max(dp[k])

Source