[C++] : From Backtracking to DP + Bit masking
Approch 1 : Using Backtracking\n\nclass Solution {\npublic:\n    \n    int calculate_score(vector<int> &a, vector<int> &b)\n    {\n        int ans = 0;\n       
Approch 1 : Using Backtracking\n```\nclass Solution {\npublic:\n    \n    int calculate_score(vector<int> &a, vector<int> &b)\n    {\n        int ans = 0;\n        for(int i = 0; i < a.size(); i++)\n        {\n            ans += (a[i] == b[i]);\n        }\n        return ans;\n    }\n    \n    int mx_sum(int i, vector<bool> used, vector<vector<int>> &score, int n,int m)\n    {\n        if(i >= n) return 0;\n        int ans = 0;\n        for(int j = 0; j < m; j++)\n        {\n            if(used[j]) continue;\n            used[j] = 1;\n            ans = max(ans, score[i][j] + mx_sum(i + 1, used, score, n, m));\n            used[j] = 0;\n        }\n        return ans;\n    }\n    \n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) \n    {\n        int n = students.size();\n        int m = mentors.size();\n        \n        vector<vector<int>> score(n, vector<int> (m, 0));\n        \n        for(int i = 0; i < n; i++)\n            for(int j = 0; j < m; j++)\n                score[i][j] = calculate_score(students[i], mentors[j]);\n        \n        vector<bool> used(m, 0);\n        return mx_sum(0, used, score, n, m);\n    }\n    \n};\n```\n\nApproach 2 : Using DP + mask (using mask to replace used  and to memoize results)\n```\nconst int N = 9;\nint dp[N][1 << 8];\nclass Solution {\npublic:\n    \n    int calculate_score(vector<int> &a, vector<int> &b)\n    {\n        int ans = 0;\n        for(int i = 0; i < a.size(); i++)\n        {\n            ans += (a[i] == b[i]);\n        }\n        return ans;\n    }\n    \n    int mx_sum(int i, int mask, vector<vector<int>> &score, int n,int m)\n    {\n        if(i >= n) return 0;\n        \n        if(dp[i][mask] != -1) return dp[i][mask];\n        \n        int ans = 0;\n        for(int j = 0; j < m; j++)\n        {\n            if(mask & (1 << j)) continue;\n            ans = max(ans, score[i][j] + mx_sum(i + 1, mask + (1 << j), score, n, m));\n        }\n        return dp[i][mask] = ans;\n    }\n    \n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) \n    {\n        int n = students.size();\n        int m = mentors.size();\n        \n        vector<vector<int>> score(n, vector<int> (m, 0));\n        \n        for(int i = 0; i < n; i++)\n            for(int j = 0; j < m; j++)\n                score[i][j] = calculate_score(students[i], mentors[j]);\n        \n        //global\n        for(int i = 0; i < N; i++)\n            for(int j = 0; j < (1 << 8); j++)\n                dp[i][j] = -1;\n        \n        int mask = 0;\n        return mx_sum(0, mask, score, n, m);\n    }\n    \n};\n```
['Backtracking']