AlgorithmAndLeetCode · pull · Jul 16, 2025 · Jul 16, 2025
diff --git a/README.md b/README.md
@@ -450,6 +450,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [3377. 使两个整数相等的数位操作](./problems/3377.digit-operations-to-make-two-integers-equal.md)
 - [3404. 统计特殊子序列的数目](./problems/3404.count-special-subsequences.md)
 - [3428. 至多 K 个子序列的最大和最小和](./problems/3428.maximum-and-minimum-sums-of-at-most-size-k-subsequences.md)
+- [3599. 划分数组以最小化异或值](./problems/3599.partition-array-to-minimize-xor.md)
 
 ### 困难难度题目合集
 

diff --git a/SUMMARY.md b/SUMMARY.md
@@ -286,6 +286,7 @@
   - [3377. 使两个整数相等的数位操作](./problems/3377.digit-operations-to-make-two-integers-equal.md)
   - [3404. 统计特殊子序列的数目](./problems/3404.count-special-subsequences.md)
   - [3428. 至多 K 个子序列的最大和最小和](./problems/3428.maximum-and-minimum-sums-of-at-most-size-k-subsequences.md)
+  - [3599. 划分数组以最小化异或值](./problems/3599.partition-array-to-minimize-xor.md)
 
 - [第六章 - 高频考题（困难）](collections/hard.md)
 

diff --git a/problems/3599.partition-array-to-minimize-xor.md b/problems/3599.partition-array-to-minimize-xor.md
@@ -0,0 +1,118 @@
+## 题目地址(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 表。