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

题目描述
给定一个正整数数组 nums，判断是否可以将该数组划分成两个子集，使得两个子集的元素和相等。如果可能，返回 true，否则返回 false。例如，对于数组 [1, 5, 11, 5]，可以划分成 [1, 5, 5] 和 [11]，两个子集的和均为 11，因此返回 true。

解题思路

1. 问题转化：若数组总和为奇数，直接返回 false（因为无法平分）。若总和为偶数，则目标子集和 target = sum(nums) / 2。问题转化为：是否存在子集的和为 target？这本质上是一个 0-1 背包问题。
2. 区间动态规划视角：虽然此题常用一维DP解决，但我们可以从区间DP的角度理解：定义 dp[i][j] 表示前 i 个元素是否能组成和 j。但更符合区间DP思想的解法是直接处理子数组的和关系。
3. 状态定义：设 dp[i][j] 表示从数组下标 0 到 i 的元素中，能否选出若干个数使其和为 j。
4. 状态转移：
   • 若 j >= nums[i]：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]（不选当前元素或选当前元素）。
   • 否则：dp[i][j] = dp[i-1][j]。
5. 初始化：dp[0][0] = true，dp[0][nums[0]] = true（若 nums[0] <= target）。
6. 结果：检查 dp[n-1][target] 是否为 true。

逐步详解

1. 计算总和：

   total = sum(nums)
   if total % 2 != 0:
       return False
   target = total // 2
   

2. 初始化DP表：
   创建二维数组 dp，维度为 n × (target+1)，初始化为 False。

   dp[0][0] = True
   if nums[0] <= target:
       dp[0][nums[0]] = True
   

3. 填充DP表：
   遍历每个元素 i（从 1 到 n-1），对于每个和 j（从 0 到 target）：

   if j >= nums[i]:
       dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
   else:
       dp[i][j] = dp[i-1][j]
   

4. 优化空间：
   实际可压缩为一维DP，倒序遍历 j 避免覆盖：

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

5. 返回结果：

   return dp[target]
   

实例验证
以 nums = [1, 5, 11, 5] 为例：

• 总和 = 22，target = 11。
• 初始化 dp[0]=True。
• 处理 num=1：dp[1]=True。
• 处理 num=5：dp[6]=True（由 dp[1] 推导）。
• 处理 num=11：dp[11]=True（由 dp[0] 推导）。
• 最终 dp[11] 为 True，返回 true。

关键点

• 此题的区间DP思想体现在对子数组和的逐步构建。
• 空间优化后时间复杂度为 O(n×target)，适用于 target 不大的场景。