两个数组最小的异或值之和

1. 状态压缩 + 动态规划

顺序不重要，依次枚举数组1的每个数，和数组2进行组合计算

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        if(judge(nums1)||judge(nums2)){
            int res = 0;
            for(int i=0;i<n;i++)
                res = res + (nums1[i]^nums2[i]);
            return res;
        }
        vector<int> dp(1<<n,INT_MAX);//dp[i]表示i状态下的最小亦或和
        dp[0] = 0;//初始状态亦或和为0
        for(int i=0;i<n;i++){//依次遍历数组1中的数，加入到状态中
            for(int mask=0;mask<(1<<n);mask++){//遍历所有状态
                if(__builtin_popcount(mask)==i){//从小到大
                    for(int j=0;j<n;j++){ //尝试给数组2中每一个数进行亦或
                        int state = mask|(1<<j);
                        if(state==mask) continue;
                        dp[state] = min(dp[state],dp[mask]+ (nums1[i]^nums2[j]));
                    }
                }
            }
        }
        return dp[(1<<n)-1];
    }
    bool judge(vector<int>& nums){
        for(int i=1;i<nums.size();i++)
            if(nums[i]!=nums[i-1]) return false;//表示不全相同
        return true;
    }
};