Detailed Efficient DP solution C++.
Approach\nwe want to keep track of the current day i and current city cur in the dp array\nso let\'s break down the steps:\n1- initialize dp array with -1 initi
# Approach\nwe want to keep track of the current day i and current city cur in the dp array\nso let\'s break down the steps:\n1- initialize dp array with -1 initial values.\n2- try to start the initial city from 0->n-1.\n3- for each current state try to go to any city from 0->n-1 and maximize the answer.\n\n# Complexity\n- Time complexity:the solve function O(N * N) , memset O(N * k)\n\n- Space complexity: dp array-> O(N * k), travelScore array-> O(N * N)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int dp[201][201];\n    int solve(int i, int cur, int &n, int &k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore){\n        if(i==k)return 0;\n        int &ret = dp[i][cur];\n        if(~ret) return ret;\n        ret = 0;\n        for(int j = 0;j < n;j++){\n            int res = solve(i + 1, j, n, k, stayScore, travelScore) + \n            ((cur==j) ? stayScore[i][j] : travelScore[cur][j]);\n            ret = max(ret, res);\n        }\n        return ret;\n    }\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        memset(dp, -1, sizeof(dp));\n        int ans = 0;\n        for(int i = 0;i < n;i++)\n            ans = max(ans, solve(0, i, n, k, stayScore, travelScore));\n        return ans;\n    }\n};\n```
[]