[Python3] Bitmask DP - Detailed Explanation
Intuition\n- Each student we try all possible mentor left. the total score of current student i depend on the choice of the previous mentor choice of student i 
# Intuition\n- Each student we try all possible mentor left. the total score of current student `i` depend on the choice of the previous mentor choice of student `i - 1`. It means we have explore all possible cases and which are overlap in states and find the maximum of score -> the signal of DP\n- `m` and `n` is very small which we can save the states in bit number.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Initialization:**\n- `m, n = len(students), len(students[0])`: Calculates the number of students (m) and the number of preferences per individual `n`.\n**2. Dynamic Programming (Top-Down Approach):**\n- `@cache`: This decorator is used to memoize the dp function, avoiding redundant calculations.\n- `def dp(student: int, mentor: int) -> int:`: Defines the recursive dp function.\n    - `if student == m: return 0`: If all students have been assigned, return 0 as there are no more assignments to make.\n    - `res = 0`: Initializes the maximum compatibility sum to 0.\n    - `for i in range(m):`: Iterates through all mentors.\n        - `if mentor & (1 << i): continue`: Checks if the current mentor has already been assigned. If so, skip it.\n        - `score = sum(1 for j in range(n) if students[student][j] == mentors[i][j])`: Calculates the compatibility score between the current student and mentor.\n        - `res = max(res, score + dp(student + 1, mentor | (1 << i)))`: Recursively calculates the maximum compatibility sum by assigning the current mentor to the student and exploring the remaining assignments.\n    - `return res`: Returns the maximum compatibility sum for the current state.\n- `return dp(0, 0)`: Calls the dp function with initial values of 0 for the current student and mentor indices, starting the dynamic programming process.\n\n**3. Explanation:**\n- The `dp` function uses a top-down dynamic programming approach to efficiently calculate the maximum compatibility sum.\n- The state of the assignment is represented by the `student` and `mentor` indices, and the bitmask `mentor` is used to keep track of assigned mentors.\n- The `dp` function recursively explores different combinations of mentor assignments, calculating the compatibility score for each combination and updating the maximum result.\n- The memoization decorator ensures that the `dp` function avoids recalculating results for the same state, improving efficiency.\n- The final result is the maximum compatibility sum obtained by considering all possible assignments.\n\n\n# Complexity\n- Time complexity: $$O(M * 2 ^ M * M * N)$$ ~ $$O(M ^ 2 * 2 ^ M * N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(M * 2 ^ M)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n        m, n = len(students), len(students[0])\n        @cache\n        def dp(student: int, mentor: int) -> int:\n            if student == m: return 0\n            res = 0\n            for i in range(m):\n                if mentor & (1 << i): continue\n                score = sum(1 for j in range(n) if students[student][j] == mentors[i][j])\n                res = max(res, score + dp(student + 1, mentor | (1 << i)))\n            return res\n        return dp(0, 0)\n```
['Array', 'Dynamic Programming', 'Backtracking', 'Bit Manipulation', 'Bitmask', 'Python3']