DP with Bitmasking Easy Intuititive || C++
Explanation and intuition :\n At first, the noticing fact are the problem contraints. Both m and n are less than or equals to 8.\n Also, we have to keep a track
**Explanation and intuition** :\n* At first, the noticing fact are the problem contraints. Both m and n are less than or equals to 8.\n* Also, we have to keep a track of the subset from the mentors array who have been already assigned to a particular student (can be done in the other way too).\n* Thus, these facts enhance our idea that we can use DP with bitmasks. \n* At first, make two vectors to store for each student and mentor their answer sum in decimal (as n<=8, the number will definitely fit in int).\n* e.g., [1,0,1,0,0] for a student turns 16+4=20\n* For a mentor with [1,0,0,0,1], the sum is 16+1=17\n* Thus, doing ```__builtin_popcount``` of XOR of the two sums, we get number of different bits. So just subtract it from n to get the compatibility score !\n\n* Now, coming to DP, let we will be assigning each student a particular mentor one by one. \n* Thus, f(index,mentors) -> max compatibility score for assigning students from index till end when the mentors present in "mentors" have already been assigned. \n* Let, mentor 1,2,5 have been assigned among 5 mentors. We can keep track using mask 10011 having set bits indicating the already assigned mentors (starting from right, 0-based indexing)\n* Thus, state change from index to index+1 happens ->\n\t\tFrom 1 to m, when that bit of the mask is unset. We just set it, add the compatibility score and call for next index.\n\t\tFinally, we take the max of all the sums !\n\t\t\n\t**The code :**\n\t\n\t```class Solution {\npublic:\n    \n    int dp[9][1<<8];\n    \n    int f(vector<int> &s_sum, vector<int> &t_sum, int index, int mask, int m, int n){\n        // from this index with mask \'mask\', find the max result\n        \n        if (index==m){\n            return 0;\n        }\n        \n        if (dp[index][mask]!=-1) return dp[index][mask];\n        \n        int ans=0;\n        \n        for (int j=0;j<m;j++){\n            // which teacher\n            if (mask & (1<<j)) continue;\n            // mask set\n            \n            int s_score=s_sum[index];\n            int t_score=t_sum[j];\n            int temp=s_score^t_score;\n            int to_add=n-(__builtin_popcount(temp));\n            // number of same bits\n            \n            ans=max(ans, to_add + f(s_sum, t_sum, index+1, mask|(1<<j), m, n));\n        }\n        \n        return dp[index][mask]=ans;\n    }\n    \n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n        int m=students.size();\n        int n=students[0].size();\n        \n        vector<int> s_sum(m,0);\n        for (int i=0;i<m;i++){\n            int sum=0;\n            for (int j=0;j<n;j++){\n                sum=sum*2;\n                sum+=students[i][j];\n            }\n            s_sum[i]=sum;\n        }\n        // [6,5,1] for example 1\n        \n        vector<int> t_sum(m,0);\n        for (int i=0;i<m;i++){\n            int sum=0;\n            for (int j=0;j<n;j++){\n                sum*=2;\n                sum+=mentors[i][j];\n            }\n            t_sum[i]=sum;\n        }\n        // [4,1,6] for example 1\n        \n        memset(dp,-1,sizeof(dp));\n        \n        int res=f(s_sum,t_sum,0,0,m,n);\n        \n        return res;\n    }\n};```\n\n**Time complexity** :\n\nTime complexity in DP : No. of states * transition time between states \n\nHere, no. of states = No. of indices * Total possible mask size\n\t\t\t\t\t\t\t= m*(2^m)\nTransition time is in order of O(m), basically work done in each state\n\nPrecomputation time of binary to decimal conversion : O(m*n)\n\nThus total complexity : O(m*n) + O((m^2) * (2^m)) = O(m^2 * 2^m)\n\n**Hope you like it !**
['Dynamic Programming', 'C++']