区间动态规划例题：最小划分问题（平衡划分问题）

题目描述
给定一个正整数数组 nums，要求将其划分为两个子集（每个元素只能属于一个子集），使得两个子集的元素和之差尽可能小。返回这个最小的差值。
例如：nums = [1, 6, 11, 5]，最小差值为 1（子集 [1, 5, 6] 和 [11] 的和分别为 12 和 11）。

解题思路

1. 问题转化

   • 设数组总和为 S，问题等价于：在数组中选出一个子集，其元素和尽可能接近 S/2（即背包容量为 S/2 的 0-1 背包问题）。
   • 最小差值 = S - 2 * max_subset_sum，其中 max_subset_sum 是不超过 S/2 的最大子集和。

2. 区间动态规划定义

   • 定义 dp[i][j] 为考虑前 i 个元素时，能否得到子集和 j（布尔值）。
   • 状态转移：
     • 不选第 i 个元素：dp[i][j] = dp[i-1][j]
     • 选第 i 个元素：dp[i][j] = dp[i-1][j - nums[i]]（若 j ≥ nums[i]）
   • 初始状态：dp[0][0] = true（空子集和为0）。

3. 优化空间复杂度

   • 使用一维数组 dp[j] 倒序更新（避免覆盖前一状态）。

详细步骤

步骤 1：计算总和

S = sum(nums) = 1 + 6 + 11 + 5 = 23
目标子集和上限 target = S // 2 = 11

步骤 2：初始化 DP 数组

dp = [False] * (target + 1)
dp[0] = True  # 空子集的和为0

步骤 3：遍历数组更新 DP

• 对每个元素 num，从 target 倒序更新至 num：
  • dp[j] = dp[j] or dp[j - num]

示例流程（nums = [1, 6, 11, 5]）：

1. num = 1：
   • j=11..1：更新 dp[1] = True
   • dp = [True, True, False, ..., False]
2. num = 6：
   • j=11..6：更新 dp[7] = True（因 dp[1] 为 True）
   • j=5..1：更新 dp[6] = True（直接取 num=6）
3. num = 11：
   • j=11：dp[11] = True（因 dp[0] 为 True）
4. num = 5：
   • j=11..5：更新 dp[10] = True（因 dp[5] 为 True）

步骤 4：查找最接近 target 的子集和

max_sum = 11  # dp[11] 为 True
最小差值 = 23 - 2 * 11 = 1

复杂度分析

• 时间复杂度：O(n × target)，其中 target = S/2。
• 空间复杂度：O(target)。

关键点

• 将最小划分问题转化为 子集和问题，利用背包思路求解。
• 倒序更新避免状态覆盖，确保每个元素仅使用一次。
• 最终结果是 S - 2 * max_sum，而非直接找两个子集的划分方式。