这道题是经典的状压 DP,因为数据范围 n <= 14,我们可以用一个二进制掩码表示 nums2 的使用情况。

思路

1. 定义 dp[mask]:表示已经为 nums1 的前 k 个元素(k = bits.OnesCount(mask))匹配了 nums2 中对应 mask 集合的元素,此时的最小异或和。
2. 转移时,枚举 mask 中每一个被使用的位 j(即 nums2[j] 已配对),它一定是和 nums1[k-1] 配对,所以:
   ```
   dp[mask] = min_{j ∈ mask} ( dp[mask ^ (1<<j)] + (nums1[k-1] ^ nums2[j]) )
   ```
3. 初始化 dp[0] = 0,其余为无穷大。最终答案为 dp[(1<<n) - 1]。

时间复杂度 O(n * 2^n),空间 O(2^n),对于 n=14 完全可行。

Go 实现

```go
func minimumXORSum(nums1 []int, nums2 []int) int {
    n := len(nums1)
    total := 1 << n
    dp := make([]int, total)
    for i := 1; i < total; i++ {
        dp[i] = 1 << 30 // 初始化为一个大数
    }
    // dp[0] 已为 0

    for mask := 1; mask < total; mask++ {
        // 已经匹配的 nums1 的数量
        k := bits.OnesCount(uint(mask))
        // 当前要匹配的是 nums1[k-1]
        x := nums1[k-1]
        // 尝试 mask 中每一个被选中的 nums2 元素
        for j := 0; j < n; j++ {
            if mask>>j&1 == 1 {
                prev := mask ^ (1 << j)
                val := dp[prev] + (x ^ nums2[j])
                if val < dp[mask] {
                    dp[mask] = val
                }
            }
        }
    }
    return dp[total-1]
}
```

复杂度

· 时间复杂度:O(n * 2^n)
· 空间复杂度:O(2^n)

如果想让代码在 LeetCode 上直接运行,别忘了加上 import "math/bits"。

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐