3332. Maximum Points Tourist Can Earn

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.

class Solution {
public:
    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        vector<int> dp(n);
        for(int i = 0; i < k; i++) {
            vector<int> dpp(n);
            for(int u = 0; u < n; u++) {
                for(int v = 0; v < n; v++) {
                    if(u == v) dpp[v] = max(dpp[v], dp[u] + stayScore[i][u]);
                    else dpp[v] = max(dpp[v], dp[u] + travelScore[u][v]);
                }
            }
            swap(dp,dpp);
        }
        return *max_element(begin(dp), end(dp));
    }
};