C++ | Recursive DP | Bitmasking | 3ms | 10 MB | Beats 99.62%
\n\n\nint score[8][8];\nint dp[8][1<<8];\nint n;\nint backtrack(int i, int mask){\n\tif(i==n) return 0;\n\tif(dp[i][mask]!=-1) return dp[i][mask];\n\tint ret=IN
![image](https://assets.leetcode.com/users/images/96c61c85-7568-4b3c-88c1-3f25642df2b9_1656442425.8650923.png)\n\n```\nint score[8][8];\nint dp[8][1<<8];\nint n;\nint backtrack(int i, int mask){\n\tif(i==n) return 0;\n\tif(dp[i][mask]!=-1) return dp[i][mask];\n\tint ret=INT_MIN;\n\tfor(int j=0; j<n; j++)\n\t\tif(mask&(1<<j))\n\t\tret = max(ret, score[i][j] + backtrack(i+1, mask^(1<<j)));\n\treturn dp[i][mask] = ret;\n}\nint maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n\tmemset(dp, -1, sizeof dp);\n\tmemset(score, 0, sizeof score);\n\tn=students.size();\n\tfor(int i=0; i<n; i++)\n\t\tfor(int j=0; j<n; j++)\n\t\t\tfor(int k=0; k<students[0].size(); k++)\n\t\t\t\tscore[i][j] += students[i][k]==mentors[j][k];\n\treturn backtrack(0, (1<<n)-1); //start with 1st student; with all the mentors available to assign\n//(1<<n-1 has all the n bits ON)\n}\n/*\nHint:\n\tSimilar to job assignment problem.\n*/\n```\n\nThanks \u270C
['Dynamic Programming', 'Recursion', 'C', 'Bitmask', 'C++']