Maximum Points Tourist Can Earn - Solution & Explanation

Problem Overview: You are given multiple cities and several travel days. Each day you can either stay in your current city to gain stayScore[day][city] or travel to another city to gain travelScore[from][to]. The goal is to plan movements across days to maximize the total points earned.

Approach 1: Brute Force Recursion (Exponential Time)

The most direct idea is to try every possible decision each day: either stay in the same city or travel to another one. A recursive function explores all combinations of city choices for every day. For each state (day, city), the recursion branches into staying or traveling to every other city.

This approach quickly becomes infeasible because the number of paths grows exponentially with the number of days and cities. Time complexity is O(n^k) in the worst case (where n is the number of cities and k is the number of days). Space complexity is O(k) due to recursion depth. This version mainly helps understand the decision structure before introducing dynamic programming.

Approach 2: Dynamic Programming (O(k * n^2))

Dynamic programming eliminates repeated calculations by storing the best score achievable for each state. Define dp[day][city] as the maximum points obtainable after finishing day days while ending in city. For every new day, evaluate two choices: stay in the same city or travel from any other city.

Staying adds stayScore[day][city] to dp[day-1][city]. Traveling checks all possible previous cities prev and updates the score using dp[day-1][prev] + travelScore[prev][city]. The algorithm iterates through days, then cities, and computes the best transition. Because each city considers all previous cities, the time complexity becomes O(k * n^2). The DP table requires O(k * n) space.

This solution naturally models the problem as a layered decision graph across days. Each layer represents cities for that day, and transitions represent travel or staying. The structure closely resembles problems solved with matrix transitions and state updates common in array-based DP.

Approach 3: Space Optimized Dynamic Programming (O(k * n^2), O(n) space)

The DP relation only depends on the previous day. Instead of storing a full k × n table, maintain two arrays: prev and curr. For each day, compute the best score for every city using values from prev, then swap arrays.

This reduces memory usage from O(k * n) to O(n) while preserving the same transition logic. Time complexity remains O(k * n^2) because each city still checks all possible previous cities when considering travel transitions.

Recommended for interviews: The dynamic programming approach is what interviewers expect. Starting with the brute-force recursion shows you understand the decision tree. Converting it into a DP state dp[day][city] demonstrates optimization skills and familiarity with classic multi-stage DP problems.