# 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），其他情况初始化为无穷大。
  * **优点**：避免了递归的开销，时间复杂度更优。

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

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

### 解法

#### 方法一：记忆化递归

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

```python
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))，用于记忆化缓存。

#### 方法二：动态规划

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

```python
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 表。