区间动态规划例题：统计美丽子数组的数目（位运算 + 区间DP）
字数 3492 2025-12-17 21:46:39

区间动态规划例题：统计美丽子数组的数目（位运算 + 区间DP）

问题描述
给定一个整数数组 nums，你需要统计其美丽子数组的数目。一个美丽子数组定义为：该子数组的所有元素的按位异或（XOR）结果为 0，且子数组的长度为偶数。
注意：子数组定义为原数组中连续的一段。
示例：
输入：nums = [4, 3, 1, 2, 4]
输出：2
解释：美丽子数组有 [3, 1, 2, 4]（XOR = 0，长度 4 为偶数）和 [4, 3, 1, 2, 4]（整个数组，XOR = 0，长度 5 为奇数，不满足）。
实际上，长度为 5 的整个数组 XOR 为 0，但长度不为偶数，所以不计数。
（注：本题改编自力扣第 2588 题“统计美丽子数组的数目”，但此处强调了偶数长度和区间 DP 解法，便于教学）

解题思路
本题要求子数组满足两个条件：

  1. 子数组内所有元素的 XOR 结果为 0。
  2. 子数组长度为偶数。

一个直接的想法是遍历所有子数组，计算 XOR 和长度，但时间复杂度为 O(n²)，在 n 较大时可能超时。这里我们采用区间动态规划的思路，但会结合前缀异或和哈希表进行优化。不过，为了循序渐进，我们先从最基础的区间 DP 开始，再引入优化。

步骤 1：暴力区间 DP 思路
定义 dp[i][j] 为布尔值，表示子数组 nums[i..j] 的 XOR 结果是否为 0。
转移方程：

  • 若 i == j，则 dp[i][j] = (nums[i] == 0)，因为单个数的 XOR 就是它本身，为 0 才满足条件 1。
  • 若 i < j，则 dp[i][j] = dp[i][j-1] XOR nums[j] == 0，这表示在子数组 nums[i..j-1] 的 XOR 基础上再异或 nums[j]，检查结果是否为 0。
    但注意，这里 dp[i][j-1] 存储的应该是数值（XOR 结果），而不是布尔值，所以更合适的定义是：
    xor[i][j] 表示子数组 nums[i..j] 的 XOR 结果。
    则有：
    xor[i][j] = xor[i][j-1] ^ nums[j]，且 xor[i][i] = nums[i]。

然后，我们可以在计算过程中判断：若 xor[i][j] == 0 且 (j-i+1) % 2 == 0，则计数加一。

时间复杂度：O(n²) 计算所有子数组的 XOR，空间 O(n²) 存储 xor 表。
这已经比 O(n³) 的暴力好，但还可优化。

步骤 2：前缀异或优化
我们知道，子数组 nums[i..j] 的 XOR 可以通过前缀异或快速得到：
设 prefix_xor[k] 表示 nums[0..k] 的 XOR 结果（约定 prefix_xor[-1] = 0，即空数组的 XOR 为 0）。
则 nums[i..j] 的 XOR = prefix_xor[j] ^ prefix_xor[i-1]。

那么条件 1：prefix_xor[j] ^ prefix_xor[i-1] == 0 等价于 prefix_xor[j] == prefix_xor[i-1]。

条件 2：长度为偶数，即 (j - i + 1) % 2 == 0，等价于 (j - (i-1)) % 2 == 1，即 i-1 和 j 的奇偶性不同。

因此，问题转化为：
统计有多少对索引 (l, r) 满足 0 ≤ l < r ≤ n-1，且 prefix_xor[l] == prefix_xor[r]，且 (r - l) % 2 == 1（即 l 和 r 的奇偶性不同）。

这样，我们可以用哈希表记录每种前缀异或值出现的位置（按索引奇偶分组），然后一次遍历即可计数。

步骤 3：算法细节

  1. 初始化 prefix_xor = 0，哈希表 count，其中 count[x][parity] 表示前缀异或值为 x 且索引奇偶性为 parity 的出现次数（这里 parity = 0 表示偶数索引，1 表示奇数索引）。
  2. 遍历数组，对每个位置 j（0-based）：
    • 计算 prefix_xor ^= nums[j]。
    • 我们想找所有 l < j 使得 prefix_xor[l] == prefix_xor[j] 且 (j - l) % 2 == 1。
      等价于：l 的奇偶性与 j 不同。
      所以，答案增加 count[prefix_xor][1 - j%2]。
    • 更新 count[prefix_xor][j%2]++（注意：这里先计数再更新，因为 l < j 不能包含自身）。
  3. 返回答案。

步骤 4：例子演示
nums = [4, 3, 1, 2, 4]
初始化：prefix_xor = 0，count[0] = {0:1, 1:0}（即前缀异或 0 在索引 -1 处出现一次，奇偶性按索引位置算，约定空数组索引为 -1，奇偶性为 1 还是 0？这里索引从 0 开始，我们令 -1 的奇偶性为 1，这样 j=0 时奇偶性 0，不同）。为简化，我们可以用两个哈希表：even_count 和 odd_count 分别记录前缀异或值在偶数索引和奇数索引的出现次数。

步骤：

  • j=0, num=4, prefix_xor=4，找与 j 奇偶性不同的索引（j%2=0，找奇数索引的前缀异或等于 4 的个数）→ odd_count[4]=0，ans=0。更新 even_count[4]=1。
  • j=1, num=3, prefix_xor=7，j%2=1，找偶数索引的前缀异或等于 7 的个数 → even_count[7]=0，ans=0。更新 odd_count[7]=1。
  • j=2, num=1, prefix_xor=6，j%2=0，找奇数索引的前缀异或等于 6 的个数 → odd_count[6]=0，ans=0。更新 even_count[6]=1。
  • j=3, num=2, prefix_xor=4，j%2=1，找偶数索引的前缀异或等于 4 的个数 → even_count[4]=1，ans+=1=1。更新 odd_count[4]=1。
  • j=4, num=4, prefix_xor=0，j%2=0，找奇数索引的前缀异或等于 0 的个数 → odd_count[0]=0，ans=1。更新 even_count[0]=1。

最终 ans=1？但示例答案是 2。检查漏了哪个？
实际上，美丽子数组是 [3,1,2,4]（索引 1~4）和 [4,3,1,2,4]（整个数组，但长度为奇数，不符合条件）。等等，整个数组长度为 5 是奇数，所以不计。
那我们漏了哪个？
再检查：[4,3,1,2] 索引 0~3，XOR=4^3^1^2=4，不为 0。
[3,1,2,4] 索引 1~4，XOR=3^1^2^4=0，长度 4 为偶数，计数 1。
还有吗？[4,3,1,2,4] 长度为 5 奇数不计。
所以答案应是 1。但示例说 2，矛盾。

检查示例输入 nums = [4, 3, 1, 2, 4] 的美丽子数组：

  • 子数组 [3,1,2,4] XOR=0，长度 4，计数。
  • 子数组 [4,3,1,2,4] XOR=0，长度 5，不计数。
  • 还有 [4]? 长度 1 不计数。
  • 没有其他 XOR=0 且长度为偶数的。
    所以示例答案应为 1。但题目描述中写输出 2，可能是笔误，或者是另一个例子。我们以实际计算为准。

步骤 5：复杂度分析

  • 时间复杂度：O(n)，一次遍历。
  • 空间复杂度：O(m)，m 为不同前缀异或值的个数，最坏 O(n)。

总结
本题从最朴素的区间 DP 定义出发，通过前缀异或和奇偶性条件，转化为哈希计数问题，实现 O(n) 时间复杂度的优美解法。核心是：

  1. 用前缀异或将子数组 XOR 归零转化为前缀值相等。
  2. 长度偶数条件转化为两端索引奇偶性不同。
  3. 用哈希表分组计数，一次遍历统计。

通过这个例子，你可以看到区间 DP 问题有时可以通过数学变换转化为更简单的问题，从而避免 O(n²) 的 DP 表。

区间动态规划例题：统计美丽子数组的数目（位运算 + 区间DP） 问题描述 给定一个整数数组 nums ，你需要统计其 美丽子数组 的数目。一个 美丽子数组 定义为：该子数组的所有元素的 按位异或（XOR） 结果为 0，且子数组的长度为 偶数 。 注意：子数组定义为原数组中连续的一段。 示例： 输入： nums = [4, 3, 1, 2, 4] 输出： 2 解释：美丽子数组有 [3, 1, 2, 4] （XOR = 0，长度 4 为偶数）和 [4, 3, 1, 2, 4] （整个数组，XOR = 0，长度 5 为奇数，不满足）。 实际上，长度为 5 的整个数组 XOR 为 0，但长度不为偶数，所以不计数。 （注：本题改编自力扣第 2588 题“统计美丽子数组的数目”，但此处强调了偶数长度和区间 DP 解法，便于教学） 解题思路 本题要求子数组满足两个条件： 子数组内所有元素的 XOR 结果为 0。 子数组长度为偶数。 一个直接的想法是遍历所有子数组，计算 XOR 和长度，但时间复杂度为 O(n²)，在 n 较大时可能超时。这里我们采用 区间动态规划 的思路，但会结合 前缀异或 和 哈希表 进行优化。不过，为了循序渐进，我们先从最基础的区间 DP 开始，再引入优化。 步骤 1：暴力区间 DP 思路 定义 dp[i][j] 为布尔值，表示子数组 nums[i..j] 的 XOR 结果是否为 0。 转移方程： 若 i == j ，则 dp[i][j] = (nums[i] == 0) ，因为单个数的 XOR 就是它本身，为 0 才满足条件 1。 若 i < j ，则 dp[i][j] = dp[i][j-1] XOR nums[j] == 0 ，这表示在子数组 nums[i..j-1] 的 XOR 基础上再异或 nums[j] ，检查结果是否为 0。 但注意，这里 dp[i][j-1] 存储的应该是数值（XOR 结果），而不是布尔值，所以更合适的定义是： xor[i][j] 表示子数组 nums[i..j] 的 XOR 结果。 则有： xor[i][j] = xor[i][j-1] ^ nums[j] ，且 xor[i][i] = nums[i] 。 然后，我们可以在计算过程中判断：若 xor[i][j] == 0 且 (j-i+1) % 2 == 0 ，则计数加一。 时间复杂度：O(n²) 计算所有子数组的 XOR，空间 O(n²) 存储 xor 表。 这已经比 O(n³) 的暴力好，但还可优化。 步骤 2：前缀异或优化 我们知道，子数组 nums[i..j] 的 XOR 可以通过前缀异或快速得到： 设 prefix_xor[k] 表示 nums[0..k] 的 XOR 结果（约定 prefix_xor[-1] = 0 ，即空数组的 XOR 为 0）。 则 nums[i..j] 的 XOR = prefix_xor[j] ^ prefix_xor[i-1] 。 那么条件 1： prefix_xor[j] ^ prefix_xor[i-1] == 0 等价于 prefix_xor[j] == prefix_xor[i-1] 。 条件 2：长度为偶数，即 (j - i + 1) % 2 == 0 ，等价于 (j - (i-1)) % 2 == 1 ，即 i-1 和 j 的奇偶性不同。 因此，问题转化为： 统计有多少对索引 (l, r) 满足 0 ≤ l < r ≤ n-1 ，且 prefix_xor[l] == prefix_xor[r] ，且 (r - l) % 2 == 1 （即 l 和 r 的奇偶性不同）。 这样，我们可以用哈希表记录每种前缀异或值出现的位置（按索引奇偶分组），然后一次遍历即可计数。 步骤 3：算法细节 初始化 prefix_xor = 0 ，哈希表 count ，其中 count[x][parity] 表示前缀异或值为 x 且索引奇偶性为 parity 的出现次数（这里 parity = 0 表示偶数索引，1 表示奇数索引）。 遍历数组，对每个位置 j （0-based）： 计算 prefix_xor ^= nums[j] 。 我们想找所有 l < j 使得 prefix_xor[l] == prefix_xor[j] 且 (j - l) % 2 == 1 。 等价于： l 的奇偶性与 j 不同。 所以，答案增加 count[prefix_xor][1 - j%2] 。 更新 count[prefix_xor][j%2]++ （注意：这里先计数再更新，因为 l < j 不能包含自身）。 返回答案。 步骤 4：例子演示 nums = [4, 3, 1, 2, 4] 初始化： prefix_xor = 0 ， count[0] = {0:1, 1:0} （即前缀异或 0 在索引 -1 处出现一次，奇偶性按索引位置算，约定空数组索引为 -1，奇偶性为 1 还是 0？这里索引从 0 开始，我们令 -1 的奇偶性为 1，这样 j=0 时奇偶性 0，不同）。为简化，我们可以用两个哈希表： even_count 和 odd_count 分别记录前缀异或值在偶数索引和奇数索引的出现次数。 步骤： j=0, num=4, prefix_ xor=4，找与 j 奇偶性不同的索引（j%2=0，找奇数索引的前缀异或等于 4 的个数）→ odd_ count[ 4]=0，ans=0。更新 even_ count[ 4 ]=1。 j=1, num=3, prefix_ xor=7，j%2=1，找偶数索引的前缀异或等于 7 的个数 → even_ count[ 7]=0，ans=0。更新 odd_ count[ 7 ]=1。 j=2, num=1, prefix_ xor=6，j%2=0，找奇数索引的前缀异或等于 6 的个数 → odd_ count[ 6]=0，ans=0。更新 even_ count[ 6 ]=1。 j=3, num=2, prefix_ xor=4，j%2=1，找偶数索引的前缀异或等于 4 的个数 → even_ count[ 4]=1，ans+=1=1。更新 odd_ count[ 4 ]=1。 j=4, num=4, prefix_ xor=0，j%2=0，找奇数索引的前缀异或等于 0 的个数 → odd_ count[ 0]=0，ans=1。更新 even_ count[ 0 ]=1。 最终 ans=1？但示例答案是 2。检查漏了哪个？ 实际上，美丽子数组是 [3,1,2,4] （索引 1~4）和 [4,3,1,2,4] （整个数组，但长度为奇数，不符合条件）。等等，整个数组长度为 5 是奇数，所以不计。 那我们漏了哪个？ 再检查： [4,3,1,2] 索引 0~3，XOR=4^3^1^2=4，不为 0。 [3,1,2,4] 索引 1~4，XOR=3^1^2^4=0，长度 4 为偶数，计数 1。 还有吗？ [4,3,1,2,4] 长度为 5 奇数不计。 所以答案应是 1。但示例说 2，矛盾。 检查示例输入 nums = [4, 3, 1, 2, 4] 的美丽子数组： 子数组 [ 3,1,2,4 ] XOR=0，长度 4，计数。 子数组 [ 4,3,1,2,4 ] XOR=0，长度 5，不计数。 还有 [ 4 ]? 长度 1 不计数。 没有其他 XOR=0 且长度为偶数的。 所以示例答案应为 1。但题目描述中写输出 2，可能是笔误，或者是另一个例子。我们以实际计算为准。 步骤 5：复杂度分析 时间复杂度：O(n)，一次遍历。 空间复杂度：O(m)，m 为不同前缀异或值的个数，最坏 O(n)。 总结 本题从最朴素的区间 DP 定义出发，通过前缀异或和奇偶性条件，转化为哈希计数问题，实现 O(n) 时间复杂度的优美解法。核心是： 用前缀异或将子数组 XOR 归零转化为前缀值相等。 长度偶数条件转化为两端索引奇偶性不同。 用哈希表分组计数，一次遍历统计。 通过这个例子，你可以看到区间 DP 问题有时可以通过数学变换转化为更简单的问题，从而避免 O(n²) 的 DP 表。