Skip to content

Latest commit

 

History

History
201 lines (161 loc) · 5.8 KB

README_EN.md

File metadata and controls

201 lines (161 loc) · 5.8 KB
comments difficulty edit_url tags
true
Medium
Array
Dynamic Programming
Matrix

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

Python3

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

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

C++

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

Go

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
}

TypeScript

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