DP | Cpp
Code\ncpp []\nclass Solution {\nprivate:\n    int getMaxEarning(int currCity, int k, vector<vector<int>>& dp, vector<vector<int>>& stayScore, vector<vector<int>
# Code\n```cpp []\nclass Solution {\nprivate:\n    int getMaxEarning(int currCity, int k, vector<vector<int>>& dp, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore, int n, int maxk){\n        if(k >= maxk)return 0;\n        if(dp[k][currCity] != -1)return dp[k][currCity];\n\n        int stay = stayScore[k][currCity] + getMaxEarning(currCity, k+1, dp, stayScore, travelScore, n, maxk);\n\n        int move = 0;\n        for(int nextcity = 0; nextcity<n; nextcity++){\n            if(currCity == nextcity){\n                if(stayScore[k][currCity] > travelScore[currCity][currCity])continue;\n            }\n            move = max(move, travelScore[currCity][nextcity] + getMaxEarning(nextcity, k+1, dp, stayScore, travelScore, n, maxk));\n        }\n        return dp[k][currCity] = max(stay, move);\n        \n    }\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        vector<vector<int>> dp(k, vector<int>(n, -1));\n        int result = INT_MIN;\n        for(int i = 0; i<n; i++){//multi source\n            result = max(result, getMaxEarning(i, 0, dp, stayScore, travelScore, n, k));\n        }\n        return result;\n    }\n};\n```
[]