Maximum Points Tourist Can Earn - Practice Coding Problems

Maximum Points Tourist Can Earn - Problem

Maximum Points Tourist Can Earn

Imagine you're planning the ultimate sightseeing adventure! 🏙️ You have n cities to explore over exactly k days, and you want to maximize your experience points.

Each day, you face an exciting decision:
• Stay in your current city and earn stayScore[day][city] points
• Travel to a different city and earn travelScore[currentCity][destinationCity] points

All cities are directly connected, so you can travel anywhere! Your mission is to find the maximum possible points you can earn during your k-day journey.

Goal: Return the maximum points achievable starting from any city.
Input: Two integers n, k and two 2D arrays stayScore, travelScore
Output: Maximum points possible

Input & Output

example_1.py — Basic Case

$ Input: n = 2, k = 1 stayScore = [[2, 3]] travelScore = [[0, 2], [1, 0]]

› Output: 3

💡 Note: With only 1 day, we can either start in city 0 and stay (2 points) or start in city 1 and stay (3 points). Starting in city 1 and staying gives maximum 3 points.

example_2.py — Travel vs Stay

$ Input: n = 2, k = 2 stayScore = [[2, 3], [1, 4]] travelScore = [[0, 5], [3, 0]]

› Output: 8

💡 Note: Optimal path: Start in city 0, travel to city 1 (5 points), then stay in city 1 (4 points). Total: 5 + 4 = 9 points. Wait, let me recalculate: Start city 1, stay (3 points), stay again (4 points) = 7. Or start city 0, travel to city 1 (5 points), stay (4 points) = 9. But we need to check all starting positions properly.

example_3.py — Multiple Cities

$ Input: n = 3, k = 2 stayScore = [[1, 2, 3], [4, 5, 6]] travelScore = [[0, 2, 1], [3, 0, 2], [1, 4, 0]]

› Output: 9

💡 Note: Start in city 2, stay day 0 (3 points), stay day 1 (6 points). Total: 3 + 6 = 9 points. This is optimal among all possible starting cities and action sequences.

Constraints

1 ≤ n ≤ 200
1 ≤ k ≤ 200
n × k ≤ 1000
0 ≤ stayScore[i][j] ≤ 10⁶
0 ≤ travelScore[i][j] ≤ 10⁶
travelScore[i][i] = 0 (no points for staying via travel)

Visualization

Tap to expand

Understanding the Visualization

Choose Starting City

Pick any city to begin your k-day adventure

Daily Decision

Each day: stay and get local experience points, or travel for journey points

Build Optimal Path

Use DP to remember best score reachable at each (day, city) combination

Find Maximum

Return the highest score achievable across all starting cities

Key Takeaway

🎯 Key Insight: This is a classic dynamic programming problem where we build the optimal solution by making the best local decisions at each step, using memoization to avoid redundant calculations.

Asked in

G Google 45 a Amazon 38 f Meta 29 ⊞ Microsoft 22 Apple 18

This problem requires dynamic programming to efficiently explore all possible tourist journeys. The optimal approach uses memoization to avoid recalculating the same (day, city) states, reducing complexity from O(n^k) to O(k × n²). Key insight: the maximum points for any day depends only on the previous day's optimal results, making this a classic state-based DP problem.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Recursive)	O(n^k)	O(k)	Try all possible combinations of staying/traveling for each day
Dynamic Programming (Memoization)	O(k × n²)	O(k × n)	Optimize brute force by caching results for (day, city) states

Brute Force (Recursive) — Algorithm Steps

For each starting city, recursively explore all possibilities
At each day, try staying in current city
At each day, try traveling to every other city
Track maximum points across all paths
Return the global maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin from any city on day 0

Branch

For each day, branch into stay + travel options

Recurse

Recursively explore all branches

Backtrack

Return maximum points from each subtree

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int n, k;
int stayScore[1000][1000];
int travelScore[1000][1000];

int max(int a, int b) {
    return (a > b) ? a : b;
}

int dfs(int day, int city) {
    if (day == k) return 0;
    
    int maxPoints = 0;
    
    // Try staying
    maxPoints = max(maxPoints, stayScore[day][city] + dfs(day + 1, city));
    
    // Try traveling
    for (int nextCity = 0; nextCity < n; nextCity++) {
        if (nextCity != city) {
            maxPoints = max(maxPoints, 
                travelScore[city][nextCity] + dfs(day + 1, nextCity));
        }
    }
    
    return maxPoints;
}

int main() {
    scanf("%d %d", &n, &k);
    
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &stayScore[i][j]);
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &travelScore[i][j]);
        }
    }
    
    int result = 0;
    for (int startCity = 0; startCity < n; startCity++) {
        result = max(result, dfs(0, startCity));
    }
    
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^k)

For each of k days, we have n choices (stay + n-1 travel options), leading to n^k total combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion depth is k days, using stack space

✓ Linear Space

43.7K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Recursive) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler