Brute DP
Intuition\nImplementing the problem in the way it is said\n\n# Approach\nIt is a knapsack variant of DP if one observes.\n\n# Complexity\n- Time complexity:\nO(
# Intuition\nImplementing the problem in the way it is said\n\n# Approach\nIt is a knapsack variant of DP if one observes.\n\n# Complexity\n- Time complexity:\nO(N* N *k)\n\n- Space complexity:\nO(N* N *k)\n\n# Code\n```cpp []\nclass Solution {\npublic:\nint K;\nvector<vector<int>> dp;\n    int f(int curr, int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        if(k==0) return 0;\n        if(dp[k][curr]!=-1) return dp[k][curr];\n        int optionB= 0;\n        int optionA= f(curr, n, k-1, stayScore, travelScore)+ stayScore[K-k][curr];\n        for(int i=0; i<n; i++) {\n            if(i == curr) continue;\n            optionB= max(optionB, f(i, n, k-1, stayScore, travelScore)+ travelScore[curr][i]);\n        }\n        return dp[k][curr]= max(optionA, optionB);\n    }\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        int ans= 0;\n        K= k;\n        dp.resize(k+1, vector<int>(n+1, -1));\n        for(int i=0; i<n; i++) {\n            ans= max(ans, f(i, n, k, stayScore, travelScore));\n        }\n        return ans;\n    }\n};\n```
[]