Array
Dynamic Programming
Matrix
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 Java C++ Go TypeScript
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 ]);
}
GitHub