# Maximum Points Tourist Can Earn
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-points-tourist-can-earn)
Canonical: https://scaleengineer.com/dsa/problems/maximum-points-tourist-can-earn
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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` **0-indexed** days, and they can choose **any** city as their starting point.

Each day, the tourist has two choices:

* **Stay in the current city**: If the tourist stays in their current city `curr` during day `i`, they will earn `stayScore[i][curr]` points.
* **Move to another city**: If the tourist moves from their current city `curr` to city `dest`, they will earn `travelScore[curr][dest]` points.

Return the **maximum** possible points the tourist can earn.

**Example 1:**

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

**Output:** 3

**Explanation:**

The tourist earns the maximum number of points by starting in city 1 and staying in that city.

**Example 2:**

**Input:** n = 3, k = 2, stayScore = \[\[3,4,2\],\[2,1,2\]\], travelScore = \[\[0,2,1\],\[2,0,4\],\[3,2,0\]\]

**Output:** 8

**Explanation:**

The tourist earns the maximum number of points by starting in city 1, staying in that city on day 0, and traveling to city 2 on day 1.

**Constraints:**

* `1 <= n <= 200`
* `1 <= k <= 200`
* `n == travelScore.length == travelScore[i].length == stayScore[i].length`
* `k == stayScore.length`
* `1 <= stayScore[i][j] <= 100`
* `0 <= travelScore[i][j] <= 100`
* `travelScore[i][i] == 0`

# Approaches
## Brute-Force Recursion
This approach explores every possible sequence of decisions the tourist can make over the `k` days. A path is defined by a starting city and the sequence of cities visited. We can use a recursive function to explore all paths, calculate the score for each, and find the maximum.
**Time:** O(n * n^k)

For each starting city, the recursive function explores a tree of decisions. The depth of the tree is `k`, and the branching factor at each node is `n` (1 stay choice, `n-1` move choices). This leads to approximately `n^k` paths. Since there are `n` possible starting cities, the total time complexity is `O(n * n^k)`. · **Space:** O(k)

The space complexity is determined by the maximum depth of the recursion stack, which is equal to the number of days, `k`.
**Pros:** Simple to understand and implement based on the problem description.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; The time complexity makes it infeasible for the given constraints.
### Explanation
We define a recursive function, say `findMaxScore(day, currentCity)`. This function calculates the maximum score obtainable from `day` until `k-1`, given the tourist is in `currentCity` at the start of `day`. The base case for the recursion is when `day == k`, meaning the journey is over, so we return 0. In the recursive step for `findMaxScore(day, currentCity)`, we calculate the score for two choices:

1.  **Stay**: The score is `stayScore[day][currentCity] + findMaxScore(day + 1, currentCity)`.
2.  **Move**: We iterate through all possible destination cities `dest` (where `dest != currentCity`). The score for moving to `dest` is `travelScore[currentCity][dest] + findMaxScore(day + 1, dest)`. We take the maximum score among all possible destinations.

The function returns the maximum of the "stay" and "move" scores. The main function will call `findMaxScore(0, startCity)` for every possible `startCity` from `0` to `n-1` and take the maximum result. This approach is extremely slow because it recomputes the same subproblems multiple times. For example, `findMaxScore(day, city)` will be called for many different paths that lead to `city` on `day`.

```java
// This is a conceptual illustration. It will time out for the given constraints.
class Solution {
    int n;
    int k;
    int[][] stayScore;
    int[][] travelScore;

    public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) {
        this.n = n;
        this.k = k;
        this.stayScore = stayScore;
        this.travelScore = travelScore;

        int maxScore = 0;
        // The tourist can start in any city.
        for (int startCity = 0; startCity < n; startCity++) {
            maxScore = Math.max(maxScore, findMaxScore(0, startCity));
        }
        return maxScore;
    }

    private int findMaxScore(int day, int currentCity) {
        if (day == k) {
            return 0;
        }

        // Option 1: Stay in the current city
        int stayPoints = stayScore[day][currentCity] + findMaxScore(day + 1, currentCity);

        // Option 2: Move to another city
        int movePoints = 0;
        for (int destCity = 0; destCity < n; destCity++) {
            if (destCity != currentCity) {
                movePoints = Math.max(movePoints, travelScore[currentCity][destCity] + findMaxScore(day + 1, destCity));
            }
        }

        return Math.max(stayPoints, movePoints);
    }
}
```
### Algorithm
1. Define a recursive function, say `findMaxScore(day, currentCity)`, that calculates the maximum score obtainable from `day` to `k-1`, starting in `currentCity`.
2. The base case for the recursion is when `day == k`. In this case, the journey is over, so we return 0.
3. In the recursive step, calculate the scores for the two possible choices:
    a. **Stay**: The score is `stayScore[day][currentCity] + findMaxScore(day + 1, currentCity)`.
    b. **Move**: Iterate through all other cities `dest`. The score for moving is `travelScore[currentCity][dest] + findMaxScore(day + 1, dest)`. Take the maximum over all `dest`.
4. The function returns `max(stay_score, move_score)`.
5. To get the final answer, call `findMaxScore(0, startCity)` for every possible `startCity` and return the overall maximum.

## Dynamic Programming
A more efficient approach is to use dynamic programming to avoid recomputing results for the same subproblems. We can build a table `dp[i][j]` to store the maximum score achievable at the beginning of day `i`, ending in city `j`.
**Time:** O(k * n^2)

We iterate through `k` days. For each day, we compute `n` new DP states. Each state `dp[i+1][j]` requires an inner loop of size `n` to consider all possible previous cities. This results in a total time complexity of `O(k * n * n)`. · **Space:** O(k * n)

We use a DP table of size `(k+1) x n` to store the maximum scores for each day and city.
**Pros:** Guarantees finding the optimal solution.; Significantly more efficient than brute force.; Feasible for the given problem constraints.
**Cons:** Uses O(k * n) space, which might be large if `k` and `n` are very large.
### Explanation
We define `dp[i][j]` as the maximum score accumulated at the beginning of day `i`, with the tourist being in city `j`. The DP table will have dimensions `(k+1) x n`.

**Initialization**: At the beginning of day 0 (i.e., `i=0`), the tourist can start in any city with a score of 0. So, we initialize `dp[0][j] = 0` for all cities `j`.

**Recurrence Relation**: We iterate from day `i = 0` to `k-1`. To compute `dp[i+1][j]` (max score at the start of day `i+1` in city `j`), we consider all possible cities `c` the tourist could have been in at the start of day `i`.

*   If the tourist was in city `j` and stayed: The score would be `dp[i][j] + stayScore[i][j]`.
*   If the tourist was in city `c != j` and moved: The score would be `dp[i][c] + travelScore[c][j]`.

The value `dp[i+1][j]` is the maximum of all these possibilities. This is equivalent to a top-down recursive approach with memoization, which avoids the redundant calculations of the brute-force method.

**Final Answer**: After filling the table up to `dp[k]`, the maximum score at the end of the journey is the maximum value in the last row of the DP table, i.e., `max(dp[k][j])` for all `j` from `0` to `n-1`.

```java
class Solution {
    public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) {
        long[][] dp = new long[k + 1][n];

        // dp[i][j] = max score at the beginning of day i, in city j
        // Base case: dp[0][j] = 0 for all j, as we can start anywhere with 0 score.

        for (int i = 0; i < k; i++) { // i is the current day
            for (int j = 0; j < n; j++) { // j is the destination city for day i
                // Calculate max score from traveling to city j from any other city c
                long maxTravelScore = 0;
                for (int c = 0; c < n; c++) { // c is the city at the start of day i
                    if (c != j) {
                        maxTravelScore = Math.max(maxTravelScore, dp[i][c] + travelScore[c][j]);
                    }
                }
                
                // Calculate score from staying in city j
                long stayScoreVal = dp[i][j] + stayScore[i][j];
                
                // dp[i+1][j] is the max score at the end of day i (start of day i+1), in city j
                dp[i + 1][j] = Math.max(stayScoreVal, maxTravelScore);
            }
        }

        long maxTotalScore = 0;
        for (int j = 0; j < n; j++) {
            maxTotalScore = Math.max(maxTotalScore, dp[k][j]);
        }

        return (int) maxTotalScore;
    }
}
```
### Algorithm
1. Create a 2D DP table, `dp`, of size `(k+1) x n`.
2. `dp[i][j]` will store the maximum score at the beginning of day `i`, being in city `j`.
3. **Initialization**: Set `dp[0][j] = 0` for all `j` from `0` to `n-1`, as the tourist can start in any city with an initial score of 0.
4. **Iteration**: Loop through days `i` from `0` to `k-1`.
5. For each day `i`, loop through each possible destination city `j` from `0` to `n-1`.
6. Calculate `dp[i+1][j]` using the recurrence relation:
   `dp[i+1][j] = max(dp[i][j] + stayScore[i][j], max_{c != j} (dp[i][c] + travelScore[c][j]))`.
   The inner `max` is found by iterating through all possible previous cities `c`.
7. **Result**: After the loops complete, the maximum score is the maximum value in the last row of the DP table, `max(dp[k])`.

## Space-Optimized Dynamic Programming
This approach improves upon the standard dynamic programming solution by reducing the space complexity. We observe that to calculate the scores for the current day, we only need the scores from the previous day.
**Time:** O(k * n^2)

The time complexity remains the same as the standard DP approach. The nested loop structure for iterating through days, destination cities, and source cities is unchanged. · **Space:** O(n)

We only need two arrays of size `n` to store the DP states for the previous and current days. Therefore, the space complexity is reduced to `O(n)`.
**Pros:** Maintains the same time efficiency as the standard DP approach.; Highly memory efficient, using only O(n) space.; This is the most efficient solution for the given constraints.
**Cons:** The code can be slightly less intuitive to read compared to the 2D DP table version.
### Explanation
The recurrence relation `dp[i+1][j] = max(dp[i][j] + stayScore[i][j], max_{c != j} (dp[i][c] + travelScore[c][j]))` shows that the calculation for day `i+1` only depends on the results from day `i`. This means we don't need to store the entire `k x n` table.

Instead of a 2D table, we can use just two arrays of size `n`: one to store the scores of the previous day (`prevDp`) and one for the current day (`currDp`).

**Initialization**: `prevDp[j] = 0` for all `j`, representing the scores at the beginning of day 0.

**Iteration**: We loop from day `i = 0` to `k-1`. In each iteration, we compute `currDp` based on `prevDp` using the same logic as the standard DP approach. After computing `currDp` for all cities, we update `prevDp` by setting it to `currDp` for the next day's calculation.

**Final Answer**: After `k` iterations, the `prevDp` array will hold the maximum scores at the end of the journey. The result is the maximum value in this array.

```java
class Solution {
    public int maxPoints(int n, int k, int[][] stayScore, int[][] travelScore) {
        long[] prevDp = new long[n];
        // prevDp[j] = max score at the beginning of the current day, in city j
        // Initially, at day 0, score is 0 for any starting city.

        for (int i = 0; i < k; i++) { // i is the current day
            long[] currDp = new long[n];
            for (int j = 0; j < n; j++) { // j is the destination city for day i
                // Calculate max score from traveling to city j
                long maxTravelScore = 0;
                for (int c = 0; c < n; c++) { // c is the city at the start of day i
                    if (c != j) {
                        maxTravelScore = Math.max(maxTravelScore, prevDp[c] + travelScore[c][j]);
                    }
                }
                
                // Calculate score from staying in city j
                long stayScoreVal = prevDp[j] + stayScore[i][j];
                
                // currDp[j] is the max score at the end of day i
                currDp[j] = Math.max(stayScoreVal, maxTravelScore);
            }
            prevDp = currDp; // Prepare for the next day
        }

        long maxTotalScore = 0;
        for (int j = 0; j < n; j++) {
            maxTotalScore = Math.max(maxTotalScore, prevDp[j]);
        }

        return (int) maxTotalScore;
    }
}
```
### Algorithm
1. Initialize an array `prevDp` of size `n` with all zeros. This represents the scores at the beginning of day 0.
2. Loop through each day `i` from `0` to `k-1`.
3. Inside the loop, create a new array `currDp` of size `n` to store the scores for the current day.
4. For each city `j` from `0` to `n-1`:
    a. Calculate the maximum score if traveling to `j` from any other city `c`: `maxTravelScore = max_{c != j} (prevDp[c] + travelScore[c][j])`.
    b. Calculate the score if staying in `j`: `stayScoreVal = prevDp[j] + stayScore[i][j]`.
    c. Set `currDp[j] = max(maxTravelScore, stayScoreVal)`.
5. After the inner loop (over `j`) finishes, update `prevDp = currDp` to prepare for the next day's calculation.
6. After the outer loop (over `i`) finishes, the final maximum score is the largest value in the `prevDp` array.

# Solutions
### Java

```java
class Solution {
public
  int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
    int[][] f = new int[k + 1][n];
    for (var g : f) {
      Arrays.fill(g, Integer.MIN_VALUE);
    }
    Arrays.fill(f[0], 0);
    for (int i = 1; i <= k; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int h = 0; h < n; ++h) {
          f[i][j] =
              Math.max(f[i][j], f[i - 1][h] + (j == h ? stayScore[i - 1][j]
                                                      : travelScore[h][j]));
        }
      }
    }
    return Arrays.stream(f[k]).max().getAsInt();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScore(int n, int k, vector<vector<int>> &stayScore,
               vector<vector<int>> &travelScore) {
    int f[k + 1][n];
    memset(f, 0xc0, sizeof(f));
    memset(f[0], 0, sizeof(f[0]));
    for (int i = 1; i <= k; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int h = 0; h < n; ++h) {
          f[i][j] = max(f[i][j], f[i - 1][h] + (j == h ? stayScore[i - 1][j]
                                                       : travelScore[h][j]));
        }
      }
    }
    return *max_element(f[k], f[k] + n);
  }
};

```

### Python

```python
class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int: f = [[- inf] * n for _ in range(k + 1)] f[0] = [0] * n for i in range(1, k + 1): for j in range(n): for h in range(n): f[i][j] = max(f[i][j], f[i - 1][h] + (stayScore[i - 1][j] if j == h else travelScore[h][j]), ) return max(f[k])

```