2d dp + memo
IntuitionThe problem is a dynamic programming problem where the goal is to maximize the total score across multiple cities, given a set of stay and travel score
# Intuition
The problem is a dynamic programming problem where the goal is to maximize the total score across multiple cities, given a set of stay and travel scores. You have n cities, k days, a set of "stay scores" (which tells you how much score you get when you stay in a city on a specific day), and "travel scores" (which tells you how much score you get when you travel from one city to another).

# Approach
- States:

You are given a 2D matrix of stayScore (where stayScore[day][city] is the score for staying in a given city on a particular day).

You are given a 2D matrix of travelScore (where travelScore[fromCity][toCity] is the score for traveling from fromCity to toCity).

- Goal:

Maximize the total score after traveling and staying in cities for k days.

- Dynamic Programming (DP):

Let's define a DP state dp[city][day] as the maximum score achievable if we start from city on day.

The recursive function solve(city, day, n, k, stayScore, travelScore) returns the maximum score possible starting from a given city on a given day, given that we have k days left.

# Complexity
- Time complexity:
O(n×k×n)

- Space complexity:
O(n*k)

# Code
```cpp []
class Solution {
public:
    vector<vector<int>> dp;
    int solve(int city, int day,int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        if(k == 0) return 0;
        if(dp[city][day] != -1) return dp[city][day];
        int stay = stayScore[day][city] + solve(city,day+1,n,k-1,stayScore,travelScore);

        int notstay = 0;

        // O(n)
        for(int i=0;i<n;i++) {
            notstay = max(notstay, travelScore[city][i] + solve(i,day+1,n,k-1,stayScore,travelScore));
        }

        return dp[city][day]=max(stay,notstay);
    }

    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        dp.resize(n,vector<int>(k,-1));
        int ans = 0;
        for(int i=0;i<n;i++) {
            int v = solve(i,0,n,k,stayScore,travelScore);
            ans = max(v,ans);
        }

        return ans;
    }
};
```
['C++']