https://leetcode.com/problems/minimum-xor-sum-of-two-arrays/
典型的状态压缩DP的题目吧，用mask表示选择的状态！

个人解答

  1. class Solution:
  2.     def minimumXORSum(self, a: List[int], b: List[int]) -> int:
  3.         @cache
  4.         def dp(mask):
  5.             i = mask.bit_count()
  6.             if i >= len(a):
  7.                 return 0
  8.             return min((a[i] ^ b[j]) + dp(mask | (1 << j)) for j in range(len(b)) if (mask & (1 << j) == 0))
  10.         return dp(0)

题目分析

对于这种从n中选取m个，如果n不是很大的话，通常可以考虑用二进制数中的1/0表示选取与否，这样省去了自己全排列的麻烦。

参考：https://leetcode.com/problems/minimum-xor-sum-of-two-arrays/discuss/1238641/Bit-Mask
所说的一句话，很清楚：

For each position i in the first array, we’ll try all elements in the second array that haven’t been chosen before. We can use a bit mask to represent the chosen elements. To avoid re-computing the same subproblem, we memoise the result for each bit mask.

本质上就是遍历，为了记录之前的状态，用了bitmask的方式。

就本题目而言，mask中的1表示b中对应的元素被选中的状态，此时，已选择了c = mask.bit_count()个元素。这些元素与a中的前c个元素对应匹配。
那么，dp的递推关系也就比较清楚了：对于第i+1个元素a[i], 挨个与剩下的b中的元素匹配，只不过匹配的时候要利用mask，找到b中未匹配的元素。