Beginner Friendly DP Approach
IntuitionTrying all possible casesApproachComplexity

Time complexity:


O(n*k)


Space complexity:


O(n*k)

Code
# Intuition
Trying all possible cases

# Approach
     Dynamic Programming

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

- Space complexity:
- O(n*k)

# Code
```cpp []
class Solution {
public:
    int n, k, dp[205][205];
    int fun(int cur, int day, vector<vector<int>>& stay, vector<vector<int>>& travel){
        int prof = 0;
        if(day >= k){
            return 0;
        }
        if(dp[cur][day] != -1){
            return dp[cur][day];
        }
        // travel from cur city to i'th city
        for(int i = 0; i < n; i++){
            prof = max(prof, fun(i, day+1, stay, travel)+travel[cur][i]);
        }
        // staying in cur city on day+1'th day
        prof = max(prof, stay[day][cur]+fun(cur, day+1, stay, travel));
        return dp[cur][day] = prof;
    }
    int maxScore(int nn, int kk, vector<vector<int>>& stay, vector<vector<int>>& travel) {
        n = nn; k = kk;
        for(int i = 0; i <= n+2; i++){
            for(int j = 0; j <= k+2; j++){
                dp[i][j] = -1;
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res, fun(i, 0, stay, travel));
        }
        return res;
    }
};
```
['C++']