3599. 划分数组以最小化异或值

题目地址(3599. 划分数组以最小化异或值)

https://leetcode.cn/problems/partition-array-to-minimize-xor/

题目描述

给定一个整数数组 nums 和一个整数 k，你需要将数组划分为 恰好 k 个非空子数组，使得所有子数组的异或值中的 最大值 最小化。返回这个最小的最大异或值。

示例 1：

输入：nums = [0, 1, 2], k = 2
输出：2
解释：可以将数组划分为 [0, 1] 和 [2]，异或值分别为 1 和 2，最大值为 2。

示例 2：

输入：nums = [1, 2, 3, 4], k = 3
输出：4
解释：可以将数组划分为 [1, 2], [3], [4]，异或值分别为 3, 3, 4，最大值为 4。

约束：

• (1 \leq k \leq nums.length \leq 1000)

• (0 \leq nums[i] < 2^{30})

思路

首先，看数据规模，不难想到解法应该是需要多重循环的那种。

其次，题目是极小化最大值，先考虑能不能用二分。（极大化最小值也是一样的）。想了一下，似乎没好的思路。

然后，接着想，对于每一个元素 nums[i] 是不是要么合并到前面的子数组，要么单独开辟一个新的子数组。这好像是典型的”选择“问题，应该用动态规划。想到这里就差不多解决了一大半困难了。

我们可以通过两种方法解决这个问题：

• 方法一：记忆化递归（Top-Down DP）

  • 状态定义：定义 dp(i, k) 表示从第 i 个元素开始，将剩余部分划分为 k 个子数组时，能得到的最小最大异或值。

  • 递推关系：对于每个起始位置 i，我们可以尝试不同的结束位置 j，计算子数组 [i, j] 的异或值，然后递归处理剩余部分。最终结果是所有可能划分中，最大异或值的最小值。

  • 剪枝优化：如果当前计算的异或值已经大于当前最优解，则无需继续递归。

  • 缺点：由于递归深度和重复计算较多，在大数据规模下可能会超时。

• 方法二：动态规划（Bottom-Up DP）

  • 状态定义：定义 dp[i][j] 表示从第 i 个元素开始，划分为 j 个子数组时，能得到的最小最大异或值。

  • 递推关系：从后向前遍历数组，对于每个位置 i 和剩余划分数 j，枚举子数组的结束位置，计算异或值并更新最优解。

  • 初始化：dp[n][0] = 0（没有元素时划分为 0 个子数组，结果为 0），其他情况初始化为无穷大。

  • 优点：避免了递归的开销，时间复杂度更优。

两种方法的核心都是通过动态规划找到最优划分方案，区别在于递归和迭代的实现方式。以及如果用迭代对于剪枝的优化效果会更明显。

实际操作的过程，不熟悉的同学可以先递归，对于无法通过的题目可以尝试修改为动态规划。等熟练后建议大家数据规模不大递归即可，数据规模稍微有点大，直接动态规划。

解法

方法一：记忆化递归

我们使用带记忆化的自顶向下方法来高效计算结果。

from functools import cache
from math import inf

class Solution:
    def minXor(self, nums: List[int], k: int) -> int:
        @cache
        def dp(i: int, k: int) -> int:
            if i == len(nums):
                return 0 if k == 0 else inf
            ans = inf
            xor = 0
            for j in range(i, len(nums)):
                xor ^= nums[j]
                if xor >= ans: continue  # 剪枝
                ans = min(ans, max(xor, dp(j + 1, k - 1)))
            return ans

        return dp(0, k)

复杂度：

• 时间复杂度：(O(n^2 \cdot k))，其中 (n) 是 nums 的长度。每个状态 (i, k) 需要 (O(n)) 时间计算，共有 (O(n \cdot k)) 个状态。

• 空间复杂度：(O(n \cdot k))，用于记忆化缓存。

方法二：动态规划

自底向上的动态规划方法通过迭代构建解，避免了递归开销。

from math import inf

class Solution:
    def minXor(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[inf] * (k + 1) for _ in range(n + 1)]
        dp[n][0] = 0

        for i in range(n - 1, -1, -1):
            for remaining_k in range(1, k + 1):
                xor = 0
                ans = inf
                for j in range(i, n):
                    xor ^= nums[j]
                    if xor >= ans: continue  # 剪枝
                    ans = min(ans, max(xor, dp[j + 1][remaining_k - 1]))
                dp[i][remaining_k] = ans

        return dp[0][k]

复杂度：

• 时间复杂度：(O(n^2 \cdot k))，由于三重循环。

• 空间复杂度：(O(n \cdot k))，用于 DP 表。