2D-DP.
ApproachThe approach is all about figuring out the best way to maximize the tourist's score over k days by deciding whether to stay in the current city or trave
# Approach
The approach is all about figuring out the best way to maximize the tourist's score over **k days** by deciding whether to stay in the current city or travel to another one each day. To make this efficient, we use a **top-down dynamic programming** technique with a table (`dp`) to remember results we've already calculated. This way, if we end up in the same city on the same day in a different path, we don’t redo all the work—we just reuse the stored result. For each day and city, we calculate two things: the score if the tourist stays in the current city and the score if they travel to a different city. The recursion works its way through all possible choices, and when it’s done, we pick the best score across all cities as the starting point. By using this method, we avoid unnecessary repetitive calculations and efficiently find the maximum score possible.

# Complexity
- Time complexity:
O(n*k).

- Space complexity:
O(n*k).

# Code
```cpp []
class Solution {
public:
    int maxScore(int n, int k, vector<vector<int>>& stayScore,
                 vector<vector<int>>& travelScore) {
        int res = INT_MIN;
        vector<vector<int>> dp(k+1,vector<int>(n+1,-1));
        for (int i = 0; i < n; i++) {
            res = max(res, helper(n, k, 0, i, stayScore, travelScore, dp));
        }
        return res;
    }
    int helper(int n, int k, int day, int curr, vector<vector<int>>& stayScore,
               vector<vector<int>>& travelScore, vector<vector<int>>& dp) {
        if (day >= k)
            return 0;
        if(dp[day][curr] != -1)
        return dp[day][curr];
        int stay = stayScore[day][curr] +
                   helper(n, k, day + 1, curr, stayScore, travelScore, dp);
        int travel = 0;
        for (int i = 0; i < n; i++) {
            if (i == curr)
                continue;
            travel = max(travel,
                         travelScore[curr][i] +
                             helper(n, k, day + 1, i, stayScore, travelScore, dp));
        }
        return dp[day][curr] = max(stay, travel);
    }
};
```
['C++']