Skip to content

3332. Maximum Points Tourist Can Earn

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 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

Solutions

Solution 1

Thinking

Over \(k\) days we may stay or travel, scoring stay points or travel points. With \(n,k \le 200\) the state space is \(O(nk)\) and each transition enumerates the previous city.

\(f[i][j]\) is the best score after day \(i\) in city \(j\). Staying from \(h=j\) adds \(\textit{stayScore}[i-1][j]\); travelling from \(h\) adds \(\textit{travelScore}[h][j]\).

Day \(0\) has score \(0\) in every city. The answer is the maximum of \(f[k]\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maxScore(n int, k int, stayScore [][]int, travelScore [][]int) (ans int) {
    f := make([][]int, k+1)
    for i := range f {
        f[i] = make([]int, n)
        for j := range f[i] {
            f[i][j] = math.MinInt32
        }
    }
    for j := 0; j < n; j++ {
        f[0][j] = 0
    }
    for i := 1; i <= k; i++ {
        for j := 0; j < n; j++ {
            f[i][j] = f[i-1][j] + stayScore[i-1][j]
            for h := 0; h < n; h++ {
                if h != j {
                    f[i][j] = max(f[i][j], f[i-1][h]+travelScore[h][j])
                }
            }
        }
    }
    for j := 0; j < n; j++ {
        ans = max(ans, f[k][j])
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function maxScore(n: number, k: number, stayScore: number[][], travelScore: number[][]): number {
    const f: number[][] = Array.from({ length: k + 1 }, () => Array(n).fill(-Infinity));
    f[0].fill(0);
    for (let i = 1; i <= k; ++i) {
        for (let j = 0; j < n; ++j) {
            for (let 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 Math.max(...f[k]);
}

Comments