区间动态规划例题：最小划分问题

题目描述
给定一个正整数数组 nums，要求将其划分为两个子集（每个元素只能属于一个子集），使得两个子集的元素和之差尽可能小。返回这个最小的差值。

例如：
输入：nums = [1, 6, 11, 5]
输出：1
解释：子集 [1, 5, 6] 和 [11] 的和分别为 12 和 11，差值为 1。

解题思路

1. 问题转化

   • 设数组总和为 S，其中一个子集的和为 X，则另一个子集和为 S - X，差值可表示为 |(S - X) - X| = |S - 2X|。
   • 问题转化为：在数组中选若干元素，使其和 X 尽可能接近 S/2，则最小差值为 S - 2X。

2. 动态规划定义

   • 定义 dp[i][j] 表示前 i 个元素中是否存在一个子集，其和恰好为 j。
   • 状态转移方程：
     • 若 j >= nums[i-1]：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]]
     • 否则：dp[i][j] = dp[i-1][j]

3. 优化空间

   • 使用一维数组 dp[j] 代替二维数组，从后向前遍历避免覆盖。

4. 求解最小差值

   • 遍历 j 从 S/2 向下到 0，找到最大的 j 使得 dp[j] = true，则最小差值为 S - 2j。

详细步骤

1. 计算总和

   S = sum(nums)
   target = S // 2
   

2. 初始化 DP 数组

   • dp[0] = true（空子集和为 0），其余为 false。

3. 填充 DP 数组

   dp = [False] * (target + 1)
   dp[0] = True
   for num in nums:
       for j in range(target, num - 1, -1):
           if dp[j - num]:
               dp[j] = True
   

4. 查找最接近 target 的和

   for j in range(target, -1, -1):
       if dp[j]:
           return S - 2 * j
   

示例演示
以 nums = [1, 6, 11, 5] 为例：

• S = 23，target = 11
• DP 过程：
  • 初始：dp = [True, False, ..., False]
  • 加入 1：dp[1] = True
  • 加入 6：dp[7] = True
  • 加入 11：dp[11] = True（因为 dp[0] 为 True）
  • 加入 5：更新 dp[6]、dp[12]（超过 target 忽略）
• 最终 dp[11] = True，最小差值 = 23 - 2*11 = 1

复杂度分析

• 时间复杂度：O(n × S)，其中 S 为数组总和。
• 空间复杂度：O(S)。

这种方法通过动态规划高效地解决了最小划分问题，确保了正确性和最优性。