Leetcode 1947. Maximum Compatibility Score Sum

Problem statement

https://leetcode.com/problems/maximum-compatibility-score-sum/

Solution

This problem is very similar to problem Problem 1879 Minimum XOR Sum of Two Arrays.

Complexity

Time complexity is O(2^n * n * m), space complexity is O(2^n * n).

Code

class Solution:
    def maxCompatibilitySum(self, A, B):
        @lru_cache(None)
        def score(i, j):
            return sum(x==y for x,y in zip(A[i], B[j]))

        @lru_cache(None)
        def dp(mask, i):
            if i == n: return 0
            return max(dp(mask ^ (1<<j), i + 1) + score(i, j) for j in range(n) if mask & 1<<j)
        
        n = len(A)
        return dp((1<<n) - 1, 0)