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

Let dp[i][j] be the maximum points the tourist can earn starting from day i at city

Related Tags