[Python] DP bitmask with explanation (faster than 92%)
Solution from @ye15 https://leetcode.com/problems/maximum-compatibility-score-sum/discuss/1360746/Python3-permutations\n\nBut I use dp dict instead of python @c
Solution from @ye15 https://leetcode.com/problems/maximum-compatibility-score-sum/discuss/1360746/Python3-permutations\n\nBut I use dp dict instead of python @cache decorator.\nIt took me a while to understand the solution. So I want to write an explantaion to save some time for other.\n\nFirst step is easy. Calculate the score for all pairs of student and mentor.\n\nBut trying all the permutations is tricky.\nBecause the total number of students is m. 1 <= m <= 8.\nWe can use integer instead of bit. Max mask is 1 << 8 == 256\n\n**For example:**\n\nn = 3\nMask 000 means three students are not assigned.\nMask 100 means student 2 is assigned.\n\nSo basically assign all possible students to mentor 2 and then mentor 1 and then mentor 0.\nUse mask to record the visited concept of DFS.\nUse dp to record the calculated result for same input.\n\n**Most tricky parts:**\n\nif not (mask & (1 << i)):\nIf student i is not assigned.\n\nmask ^ (1<<i)   \nFlip the bit to 1. Mark the student assigned.\n\n```\nclass Solution:\n    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n        m = len(students)\n        score = [[0] * m for _ in range(m)]\n\t\t\n\t\t# Calculate the score for all pairs of student and mentor\n        for i in range(m): \n            for j in range(m): \n                score[i][j] = sum(x == y for x, y in zip(students[i], mentors[j]))\n        \n\t\t# Memorize the max result for same input (mask, j)\n        dp = {}\n\t\t\n\t\t# Find all possible student i. Assign student i to mentor j.\n\t\t# Mask is used to record assigned students.\n        def assign(mask, j): \n\t\t\t# This if can be removed. Assign function will stop when all students are assigned.\n\t\t\t# But it\'s easier to understand.\n\t\t\tif j < 0:\n\t\t\t\treturn 0\n\t\t\t# Mask, j calculated. Return the result from dp dict.\n            if (mask,j) in dp:\n                return dp[(mask,j)]\n\t\t\t\t\n            ans = 0\n            for i in range(m): \n\t\t\t\t# Find all unassigned students\n                if not (mask & (1<<i)): \n\t\t\t\t\t# Flip the unassigned student index to 1 in mask\n\t\t\t\t\t# Assign student i to mentor j\n                    ans = max(ans, assign(mask ^ (1 << i), j - 1) + score[i][j])\n            dp[(mask,j)] = ans        \n            return ans \n        \n        return assign(0, m-1)\n```
['Dynamic Programming', 'Bitmask']