Skip to content

3332. Maximum Points Tourist Can Earn 👍

Approach 1: 2D DP

  • Time: $O(n^2k)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int maxScore(int n, int k, vector<vector<int>>& stayScore,
               vector<vector<int>>& travelScore) {
    // dp[i][j] := the maximum score after i days being at city j
    vector<vector<int>> dp(k + 1, vector<int>(n));

    for (int i = 1; i <= k; ++i)
      for (int dest = 0; dest < n; ++dest) {
        // 1. Stay at the current city.
        dp[i][dest] = dp[i - 1][dest] + stayScore[i - 1][dest];
        // 2. Travel from any other city.
        for (int curr = 0; curr < n; ++curr)
          if (curr != dest)
            dp[i][dest] =
                max(dp[i][dest], dp[i - 1][curr] + travelScore[curr][dest]);
      }

    return ranges::max(dp[k]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
    // dp[i][j] := the maximum score after i days being at city j
    int[][] dp = new int[k + 1][n];

    for (int i = 1; i <= k; ++i) {
      for (int dest = 0; dest < n; ++dest) {
        // 1. Stay at the current city.
        dp[i][dest] = dp[i - 1][dest] + stayScore[i - 1][dest];
        // 2. Travel from any other city.
        for (int curr = 0; curr < n; ++curr)
          if (curr != dest)
            dp[i][dest] = Math.max(dp[i][dest], dp[i - 1][curr] + travelScore[curr][dest]);
      }
    }

    return Arrays.stream(dp[k]).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def maxScore(
      self,
      n: int,
      k: int,
      stayScore: list[list[int]],
      travelScore: list[list[int]]
  ) -> int:
    # dp[i][j] := the maximum score after i days being at city j
    dp = [[0] * n for _ in range(k + 1)]

    for i in range(1, k + 1):
      for dest in range(n):
        # 1. Stay at the current city.
        dp[i][dest] = dp[i - 1][dest] + stayScore[i - 1][dest]
        # 2. Travel from any other city.
        for curr in range(n):
          if curr != dest:
            dp[i][dest] = max(dp[i][dest],
                              dp[i - 1][curr] + travelScore[curr][dest])

    return max(dp[k])

Approach 2: 1D DP

  • Time: $O(n^2k)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maxScore(int n, int k, vector<vector<int>>& stayScore,
               vector<vector<int>>& travelScore) {
    // dp[j] := the maximum score after days so far being at city j
    vector<int> dp(n);

    for (int i = 0; i < k; ++i) {
      vector<int> newDp(n);
      for (int dest = 0; dest < n; ++dest) {
        // 1. Stay at the current city.
        newDp[dest] = dp[dest] + stayScore[i][dest];
        // 2. Travel from any other city.
        for (int curr = 0; curr < n; ++curr)
          if (curr != dest)
            newDp[dest] = max(newDp[dest], dp[curr] + travelScore[curr][dest]);
      }
      dp = std::move(newDp);
    }

    return ranges::max(dp);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
    // dp[j] := the maximum score after days so far being at city j
    int[] dp = new int[n];

    for (int i = 0; i < k; ++i) {
      int[] newDp = new int[n];
      for (int dest = 0; dest < n; ++dest) {
        // 1. Stay at the current city.
        newDp[dest] = dp[dest] + stayScore[i][dest];
        // 2. Travel from any other city.
        for (int curr = 0; curr < n; ++curr)
          if (curr != dest)
            newDp[dest] = Math.max(newDp[dest], dp[curr] + travelScore[curr][dest]);
      }
      dp = newDp; // Update dp for the next day
    }

    return Arrays.stream(dp).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def maxScore(
      self,
      n: int,
      k: int,
      stayScore: list[list[int]],
      travelScore: list[list[int]]
  ) -> int:
    # dp[j] := the maximum score after days so far being at city j
    dp = [0] * n

    for i in range(k):
      newDp = [0] * n
      for dest in range(n):
        # 1. Stay at the current city.
        newDp[dest] = dp[dest] + stayScore[i][dest]
        # 2. Travel from any other city.
        for curr in range(n):
          if curr != dest:
            newDp[dest] = max(newDp[dest],
                              dp[curr] + travelScore[curr][dest])
      dp = newDp

    return max(dp)