Hard

题目描述

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots，满足 2 * numSlots >= n。有 numSlots 个槽位，编号从 1 到 numSlots。

你需要将所有 n 个整数放入槽位中，使得每个槽位最多包含两个数字。给定放置方案的与和是每个数字与其对应槽位编号按位与运算结果的总和。

例如，将数字 [1, 3] 放入槽位 1，[4, 6] 放入槽位 2 的与和等于 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4。

返回在给定 numSlots 个槽位的情况下 nums 的最大可能与和。

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一种可能的放置方案是将 [1, 4] 放入槽位 1，[2, 6] 放入槽位 2，[3, 5] 放入槽位 3。
这给出了最大与和 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一种可能的放置方案是将 [1, 1] 放入槽位 1，[3] 放入槽位 3，[4] 放入槽位 4，[7] 放入槽位 7，[10] 放入槽位 9。
这给出了最大与和 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24。

约束条件：

  • n == nums.length
  • 1 <= numSlots <= 9
  • 1 <= n <= 2 * numSlots
  • 1 <= nums[i] <= 15

解题思路

这道题是一个经典的状态压缩动态规划问题。关键在于如何表示状态和状态转移。

状态表示：由于每个槽位最多放2个数字，我们可以用三进制来表示每个槽位的状态：

  • 0：空槽位
  • 1：放了1个数字
  • 2：放了2个数字

用一个整数 mask 表示所有槽位的状态，其中第 i 个槽位的状态为 (mask // (3^i)) % 3。

动态规划定义：dp[mask] 表示在状态 mask 下已放置数字的最大与和。

状态转移：对于每个状态 mask，计算已放置的数字个数，然后尝试将下一个数字放入每个可用的槽位中（即状态不为2的槽位），更新对应的新状态。

优化技巧：

  1. 使用记忆化搜索避免重复计算
  2. 预先计算三进制的幂次方
  3. 从数字个数多的状态开始计算，利用已有结果

时间复杂度主要由状态数量决定，为 O(3^numSlots × n)，空间复杂度为 O(3^numSlots)。

代码实现

class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n = nums.size();
        vector<int> pow3(numSlots + 1);
        pow3[0] = 1;
        for (int i = 1; i <= numSlots; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }
        
        unordered_map<int, int> dp;
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_map<int, int> newDp;
            for (auto& [mask, val] : dp) {
                for (int slot = 0; slot < numSlots; slot++) {
                    int slotState = (mask / pow3[slot]) % 3;
                    if (slotState < 2) {
                        int newMask = mask + pow3[slot];
                        int newVal = val + (nums[i] & (slot + 1));
                        newDp[newMask] = max(newDp[newMask], newVal);
                    }
                }
            }
            dp = move(newDp);
        }
        
        int result = 0;
        for (auto& [mask, val] : dp) {
            result = max(result, val);
        }
        return result;
    }
};

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)
        pow3 = [1]
        for i in range(numSlots):
            pow3.append(pow3[-1] * 3)
        
        dp = {0: 0}
        
        for num in nums:
            new_dp = {}
            for mask, val in dp.items():
                for slot in range(numSlots):
                    slot_state = (mask // pow3[slot]) % 3
                    if slot_state < 2:
                        new_mask = mask + pow3[slot]
                        new_val = val + (num & (slot + 1))
                        new_dp[new_mask] = max(new_dp.get(new_mask, 0), new_val)
            dp = new_dp
        
        return max(dp.values())

public class Solution {
    public int MaximumANDSum(int[] nums, int numSlots) {
        int n = nums.Length;
        int[] pow3 = new int[numSlots + 1];
        pow3[0] = 1;
        for (int i = 1; i <= numSlots; i++) {
            pow3[i] = pow3[i - 1] * 3;
        }
        
        Dictionary<int, int> dp = new Dictionary<int, int>();
        dp[0] = 0;
        
        foreach (int num in nums) {
            Dictionary<int, int> newDp = new Dictionary<int, int>();
            foreach (var kvp in dp) {
                int mask = kvp.Key;
                int val = kvp.Value;
                for (int slot = 0; slot < numSlots; slot++) {
                    int slotState = (mask / pow3[slot]) % 3;
                    if (slotState < 2) {
                        int newMask = mask + pow3[slot];
                        int newVal = val + (num & (slot + 1));
                        if (!newDp.ContainsKey(newMask)) {
                            newDp[newMask] = newVal;
                        } else {
                            newDp[newMask] = Math.Max(newDp[newMask], newVal);
                        }
                    }
                }
            }
            dp = newDp;
        }
        
        int result = 0;
        foreach (int val in dp.Values) {
            result = Math.Max(result, val);
        }
        return result;
    }
}

var maximumANDSum = function(nums, numSlots) {
    const n = nums.length;
    const pow3 = [1];
    for (let i = 1; i <= numSlots; i++) {
        pow3[i] = pow3[i - 1] * 3;
    }
    
    let dp = new Map();
    dp.set(0, 0);
    
    for (const num of nums) {
        const newDp = new Map();
        for (const [mask, val] of dp) {
            for (let slot = 0; slot < numSlots; slot++) {
                const slotState = Math.floor(mask / pow3[slot]) % 3;
                if (slotState < 2) {
                    const newMask = mask + pow3[slot];
                    const newVal = val + (num & (slot + 1));
                    newDp.set(newMask, Math.max(newDp.get(newMask) || 0, newVal));
                }
            }
        }
        dp = newDp;
    }
    
    return Math.max(...dp.values());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(3^numSlots × n)
空间复杂度O(3^numSlots)

其中 n 是数组长度，numSlots 是槽位数量。状态总数为 3^numSlots，每个数字需要遍历所有可能的状态转移。

相关题目