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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

Solution

Method 1 – Dynamic Programming (Bottom-Up)

Intuition

At each day and city, the tourist can either stay or move. We want to maximize the total points by making optimal choices at each step. Since the tourist can start at any city, we try all possible starting cities and use dynamic programming to avoid recomputation.

Approach

  1. Let dp[i][j] be the maximum points the tourist can earn starting from day i at city j.
  2. For the last day, the only option is to stay: dp[k-1][j] = stayScore[k-1][j] for all j.
  3. For previous days, for each city j:
    • Option 1: Stay in city j and add stayScore[i][j] to dp[i+1][j].
    • Option 2: Move to any other city m (m ≠ j), add travelScore[j][m] to dp[i+1][m].
    • Take the maximum of all options.
  4. The answer is the maximum value among all dp[0][j] (for all starting cities j).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maximumPoints(vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        int k = stayScore.size(), n = stayScore[0].size();
        vector<vector<int>> dp(k, vector<int>(n, 0));
        for (int j = 0; j < n; ++j) dp[k-1][j] = stayScore[k-1][j];
        for (int i = k-2; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                int ans = stayScore[i][j] + dp[i+1][j];
                for (int m = 0; m < n; ++m) {
                    if (m != j) ans = max(ans, travelScore[j][m] + dp[i+1][m]);
                }
                dp[i][j] = ans;
            }
        }
        return *max_element(dp[0].begin(), dp[0].end());
    }
};
 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
27
28

func maximumPoints(stayScore [][]int, travelScore [][]int) int {
    k, n := len(stayScore), len(stayScore[0])
    dp := make([][]int, k)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for j := 0; j < n; j++ {
        dp[k-1][j] = stayScore[k-1][j]
    }
    for i := k-2; i >= 0; i-- {
        for j := 0; j < n; j++ {
            ans := stayScore[i][j] + dp[i+1][j]
            for m := 0; m < n; m++ {
                if m != j && travelScore[j][m]+dp[i+1][m] > ans {
                    ans = travelScore[j][m] + dp[i+1][m]
                }
            }
            dp[i][j] = ans
        }
    }
    res := dp[0][0]
    for j := 1; j < n; j++ {
        if dp[0][j] > res {
            res = dp[0][j]
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maximumPoints(int[][] stayScore, int[][] travelScore) {
        int k = stayScore.length, n = stayScore[0].length;
        int[][] dp = new int[k][n];
        for (int j = 0; j < n; ++j) dp[k-1][j] = stayScore[k-1][j];
        for (int i = k-2; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                int ans = stayScore[i][j] + dp[i+1][j];
                for (int m = 0; m < n; ++m) {
                    if (m != j) ans = Math.max(ans, travelScore[j][m] + dp[i+1][m]);
                }
                dp[i][j] = ans;
            }
        }
        int res = dp[0][0];
        for (int j = 1; j < n; ++j) res = Math.max(res, dp[0][j]);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maximumPoints(stayScore: Array<IntArray>, travelScore: Array<IntArray>): Int {
        val k = stayScore.size
        val n = stayScore[0].size
        val dp = Array(k) { IntArray(n) }
        for (j in 0 until n) dp[k-1][j] = stayScore[k-1][j]
        for (i in k-2 downTo 0) {
            for (j in 0 until n) {
                var ans = stayScore[i][j] + dp[i+1][j]
                for (m in 0 until n) {
                    if (m != j) ans = maxOf(ans, travelScore[j][m] + dp[i+1][m])
                }
                dp[i][j] = ans
            }
        }
        return dp[0].maxOrNull() ?: 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def maximumPoints(self, stayScore: list[list[int]], travelScore: list[list[int]]) -> int:
        k, n = len(stayScore), len(stayScore[0])
        dp: list[list[int]] = [[0]*n for _ in range(k)]
        for j in range(n):
            dp[k-1][j] = stayScore[k-1][j]
        for i in range(k-2, -1, -1):
            for j in range(n):
                ans = stayScore[i][j] + dp[i+1][j]
                for m in range(n):
                    if m != j:
                        ans = max(ans, travelScore[j][m] + dp[i+1][m])
                dp[i][j] = ans
        return max(dp[0])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn maximum_points(stay_score: Vec<Vec<i32>>, travel_score: Vec<Vec<i32>>) -> i32 {
        let k = stay_score.len();
        let n = stay_score[0].len();
        let mut dp = vec![vec![0; n]; k];
        for j in 0..n {
            dp[k-1][j] = stay_score[k-1][j];
        }
        for i in (0..k-1).rev() {
            for j in 0..n {
                let mut ans = stay_score[i][j] + dp[i+1][j];
                for m in 0..n {
                    if m != j {
                        ans = ans.max(travel_score[j][m] + dp[i+1][m]);
                    }
                }
                dp[i][j] = ans;
            }
        }
        *dp[0].iter().max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maximumPoints(stayScore: number[][], travelScore: number[][]): number {
        const k = stayScore.length, n = stayScore[0].length;
        const dp: number[][] = Array.from({length: k}, () => Array(n).fill(0));
        for (let j = 0; j < n; ++j) dp[k-1][j] = stayScore[k-1][j];
        for (let i = k-2; i >= 0; --i) {
            for (let j = 0; j < n; ++j) {
                let ans = stayScore[i][j] + dp[i+1][j];
                for (let m = 0; m < n; ++m) {
                    if (m !== j) ans = Math.max(ans, travelScore[j][m] + dp[i+1][m]);
                }
                dp[i][j] = ans;
            }
        }
        return Math.max(...dp[0]);
    }
}

Complexity

  • ⏰ Time complexity: O(k * n^2), where k is the number of days and n is the number of cities. For each day and city, we check all possible moves.
  • 🧺 Space complexity: O(k * n), for the DP table.