Easy DP Solution || Recursion || Memoization
\n\n# Code\ncpp []\nclass Solution {\npublic:\n    int solve(int day, int curr_city, int k, vector<vector<int>>& stayScore,\n              vector<vector<int>>& 
\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int solve(int day, int curr_city, int k, vector<vector<int>>& stayScore,\n              vector<vector<int>>& travelScore, vector<vector<int>>& dp) {\n        if (day == k)\n            return 0;\n        if (dp[curr_city][day] != -1)\n            return dp[curr_city][day];\n        // there are 2 choices 1) stay in same citty 2)change the city\n        // 1)stay in same city\n        int stay = stayScore[day][curr_city] +\n                   solve(day + 1, curr_city, k, stayScore, travelScore, dp);\n        // 2) change  the city\n        int change = 0;\n        for (int destination = 0; destination < travelScore.size();\n             destination++) {\n            if (curr_city != destination)\n                change = max(change, solve(day + 1, destination, k, stayScore,\n                                           travelScore, dp) +\n                                         travelScore[curr_city][destination]);\n        }\n        return dp[curr_city][day] = max(stay, change);\n    }\n    int maxScore(int n, int k, vector<vector<int>>& stayScore,\n                 vector<vector<int>>& travelScore) {\n        int ans = 0;\n        vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1));\n        for (int i = 0; i < n; i++) {\n            ans = max(ans, solve(0, i, k, stayScore, travelScore, dp));\n        }\n        return ans;\n    }\n};\n```
[]