区间动态规划例题：最小划分问题（平衡划分问题） 题目描述 给定一个整数数组 nums ，你的任务是将数组划分成两个子集（不要求连续），使得两个子集的元素和尽可能接近。换句话说，你需要最小化两个子集和的绝对差。例如，对于数组 [1, 6, 11, 5] ，最优划分是子集 [1, 5, 6] （和为 12）和子集 [11] （和为 11），绝对差为 1。要求使用动态规划求解，并分析时间与空间复杂度。 解题过程 步骤 1：问题转化 设数组总和为 S 。若将数组划分为两个子集，其和分别为 sum1 和 sum2 （满足 sum1 + sum2 = S ），则绝对差为 |sum1 - sum2| = |2*sum1 - S| 。 最小化绝对差等价于找到一个子集，其和 sum1 尽可能接近 S/2 （即子集和不超过 S/2 的最大可能值）。 问题转化为经典的 0-1 背包问题 ：从数组中选择若干元素，使得其和不超过 S/2 且最大。 步骤 2：定义状态 设 dp[i][j] 表示考虑前 i 个元素时，能否得到和为 j （布尔值）。 初始状态： dp[0][0] = true （不选任何元素时和为 0），其余为 false 。 步骤 3：状态转移方程 对于第 i 个元素（数值为 nums[i-1] ）和目标和 j ： 若 j < nums[i-1] ：无法选择该元素，继承前一个状态： dp[i][j] = dp[i-1][j] 。 若 j ≥ nums[i-1] ：有两种选择： 不选该元素： dp[i][j] = dp[i-1][j] 。 选该元素： dp[i][j] = dp[i-1][j - nums[i-1]] 。 合并为逻辑或操作： dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]] 。 步骤 4：优化空间复杂度 观察发现 dp[i][j] 仅依赖 dp[i-1][...] ，可压缩为一维数组 dp[j] 。 为避免覆盖当前行未计算的值，需从后向前遍历 j （从 S/2 到 nums[i-1] ）： dp[j] = dp[j] || dp[j - nums[i-1]] 。 步骤 5：寻找最优解 遍历 j 从 S/2 向下到 0，找到第一个使 dp[j] = true 的 j ，即为不超过 S/2 的最大子集和 sum1 。 最小绝对差为 S - 2*sum1 。 步骤 6：示例演算 以 nums = [1, 6, 11, 5] 为例： 总和 S = 23 ，目标 S/2 = 11.5 ，需找不超过 11 的最大子集和。 初始化 dp[0] = true 。 遍历元素： 元素 1：更新 j=1 ， dp[1]=true 。 元素 6：从后向前更新 j=7,1 ， dp[6]=true ， dp[7]=true 。 元素 11： j≥11 不更新（因限制 j≤11）， dp[11]=true 。 元素 5：更新 j=11,10,6,5 ，得到 dp[5]=true ， dp[6]=true ， dp[10]=true ， dp[11]=true 。 最大 j=11 使 dp[11]=true ，最小差为 23 - 2*11 = 1 。 步骤 7：复杂度分析 时间复杂度：O(n * S/2)，其中 n 为数组长度。 空间复杂度：O(S/2)。 该方法通过背包思想将问题转化为可行性判断，最终找到最接近平衡的划分方案。