DP + Bitmask | 0ms Solution | With complete explanation
Here in this problem out of all the combinations between students and mentor, we have to find the optimal combination in which the score is maximum.\n\nTo do so
Here in this problem out of all the combinations between students and mentor, we have to find the optimal combination in which the score is maximum.\n\nTo do so we can use recursion to explore all the combinations.\nNow, while doing this we need to maintain track of all the mentors which have already been assigned to students, so that the new student look for only the remaining mentors.\n\nWe can easily acheive this using the visited array, by marking the mentors already assigned, but due to constraints being small we can instead easily use an integer whose ith bit will denote whether the ith mentor is aready assigned or not.\n\nTo faster up the recursion we can use memoisation on the mask, and **i need not be included in the dp** as from the mask we can easily determin the i by looking at the number of set bits.\n\nAlso finding the score between student[a] and mentor[b] takes O(n) time we can do precomputations to already store the result in DP[i][j] which denote the score between student[i] and mentor[j].\n\n```\nclass Solution {\n    int DP[8][8];\n    int dp[256] = {[0 ... 255] = -1};\n    int getMaxCompatibility(int i, int mask, vector<vector<int>>& students, vector<vector<int>>& mentors) {\n        int m = students.size(), n = students[0].size();\n        \n        if (i == m) return 0;\n        if (dp[mask] != -1) return dp[mask];\n        \n        int score = 0;\n        for(int j = 0;j<m;j++) {\n            if ((mask & (1 << j)) == 0) {\n                score = max(score, DP[i][j] + getMaxCompatibility(i+1, mask + (1 << j), students, mentors));\n            }\n        }\n        \n        return dp[mask] = score;\n    }\n    \n    \npublic:\n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n        int m = students.size(), n = students[0].size();\n\t\t\n        for(int i = 0;i<m;i++) {\n            for(int j = 0;j<m;j++) {\n                int sc = 0;\n                for(int k = 0;k<n;k++) {\n                    sc += (students[i][k] == mentors[j][k] ? 1 : 0);\n                }\n                DP[i][j] = sc;\n            }\n        }\n        \n        return getMaxCompatibility(0, 0, students, mentors);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Bitmask']