Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

• 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();
      }
  }
  
  

• 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);
      }
  };
  
  

• 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])
  
  

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

• 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]);
  }
  
  

All Problems

All Solutions