Readme

3670.Maximum-Product-of-Two-Integers-With-No-Common-Bits

解法1：Trie

比较容易想到的一个解法是将所有数字的二进制表达写入一张字典树。然后对每个num，我们从高往低遍历每个一位bit：如果bit等于1，那么我们在字典树里只能往子节点0走，如果子节点0不存在那么返回失败。如果bit等于0，那么我们优先往子节点1走；如果走下去最终返回失败，那么我们再回溯尝试往子节点0走。直至我们找到一条通往叶子节点的路径，必然是与num没有任何重合的set bits的最大数。

这样的做法容易TLE。而且记忆化需要的参数比较复杂（需要包含所在的节点以及后续的路径期望）。

解法2：DP

此题的DP做法不太常规。我们令dp[m]表示在数组里所能找到的最大的数、满足其是m的submask。因为数组元素最大值是1e6，不超过20个bit位，所以我们可以尝试计算1到(1<<k)所有数的DP值。k是数组里最大元素的二进制位数，

怎么计算dp[m]呢？我们枚举每个bit位j，则有dp[m]=max(dp[m], dp[m-(1<<j)].这样按m从小到大计算dp[m]，满足无后效性。

初始条件是对于元素里的每一个元素x，都有dp[x]=x.

在得到dp[m]之后，对于元素里的任意元素x，根据题意，它的最理想的搭配伙伴就是dp[x的补数]。其中“x的补数”就是其所有bit位的翻转，即((1<<k)-1)^x.