Simple 2D Dp solution
IntuitionApproachComplexity
Time complexity:
O(N * K)
Space complexity:
O(N * K)Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(N * K)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(N * K)

# Code
```cpp []
class Solution {
private:
vector<vector<int>> dp ;

int dfs(int day, int city, int n, int k, vector<vector<int>> &stay, vector<vector<int>> &travel)
{
    if(day == k)  return 0 ;

    if(dp[day][city] != -1)  return dp[day][city] ;

    int stayScore = dfs(day + 1, city, n, k, stay, travel) + stay[day][city] ;

    int maxTravelScore = 0 ;

    for(int destCity = 0 ; destCity < travel[city].size() ; destCity++)
    {
        if(destCity == city) continue ;

        int travelScore = dfs(day + 1, destCity, n, k, stay, travel) + travel[city][destCity] ;

        maxTravelScore = max(maxTravelScore, travelScore) ;
    }

    return dp[day][city] =  max(stayScore, maxTravelScore) ;
}

public:
    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) 
    {
        dp.resize(201, vector<int> (201, -1) ) ;

        int ans = 0 ;

        for(int i = 0 ; i < n ; i++)
        {
            int temp = dfs(0, i, n, k, stayScore, travelScore) ;

            ans = max(ans, temp) ;
        }    

        return ans ;
    }
};
```
['Dynamic Programming', 'Matrix', 'C++']