[C++, Java] Simple DP Solution 
Approach
Tow possible options we have :

stay at the current city
Move to all possible cities


Do recrusive call in this way possible and collect the maximum s

# Approach
- Tow possible options we have :
  - stay at the current city 
  - Move to all possible cities 
- Do recrusive call in this way possible and collect the maximum score


# Complexity
- Time complexity: O(N * K)

- Space complexity: O (N * K)

# Code
```cpp []
vector<vector<int>> dp;

int solve(int n, int k, int day, int curCity, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore){
    if(day >= k) return 0;
    if(dp[day][curCity] != -1) return dp[day][curCity];
    int res = stayScore[day][curCity] + solve(n, k, day + 1, curCity, stayScore, travelScore);
    for(int nextCity = 0; nextCity < n; ++nextCity){
        if(nextCity == curCity) continue;
        res = max(res, travelScore[curCity][nextCity] + solve(n, k, day + 1, nextCity, stayScore, travelScore));
    }
    return dp[day][curCity] = res;
}

int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
    dp.resize(k+1, vector<int>(n+1, -1));
    int ans = 0;
    for(int startCity = 0; startCity < n; ++startCity) ans = max(ans, solve(n, k, 0, startCity, stayScore, travelScore));
    return ans;
}
```
```java []

int[][] dp;

int solve(int n, int k, int day, int curCity, int[][] stayScore, int[][] travelScore){
    if(day >= k) return 0;
    if(dp[day][curCity] != -1) return dp[day][curCity];
    int res = stayScore[day][curCity] + solve(n, k, day + 1, curCity, stayScore, travelScore);
    for(int necxtCity = 0; necxtCity < n; ++necxtCity){
        if(necxtCity == curCity) continue;
        res = Math.max(res, travelScore[curCity][necxtCity] + solve(n, k, day + 1, necxtCity, stayScore, travelScore));
    }
    return dp[day][curCity] = res;
}

int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
    dp = new int[k+1][n+1];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1));
    int ans = 0;
    for(int startCity = 0; startCity < n; ++startCity){
        ans = Math.max(ans, solve(n, k, 0, startCity, stayScore, travelScore));
    }
    return ans;
}
```



---

<b>Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:
https://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted

---
['C++', 'Java']