区间动态规划例题：最小划分问题 题目描述 给定一个正整数数组 nums ，要求将其划分为两个子集（不一定连续），使得两个子集的元素和之差尽可能小。返回这个最小的差值。 例如： nums = [1, 6, 11, 5] ，最小差值为 1 （子集 [1, 5, 6] 和 [11] 的和分别为 12 和 11）。 解题思路 问题转化 ：设数组总和为 S ，问题等价于在数组中选出一个子集，使其元素和尽可能接近 S/2 。若子集和为 x ，则另一个子集和为 S-x ，差值 |S - 2x| 即为目标最小值。 动态规划定义 ： 定义 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 个数凑出和为 0）。 优化空间 ： 使用一维 dp[j] 倒序更新，避免覆盖上一行状态。 结果提取 ： 遍历 j 从 S/2 向下到 0，找到最大的 j 使得 dp[j] = true ，最小差值即为 S - 2*j 。 详细步骤 步骤 1：计算总和 S = sum(nums) ，目标子集和上限 target = S/2 。 步骤 2：初始化 DP 数组 dp[j] 表示能否凑出和为 j ，长度为 target + 1 。 dp[0] = true （和为 0 总是可达）。 步骤 3：状态转移 遍历每个数 num ： 从 j = target 递减到 num ： 若 dp[j - num] 为真，则 dp[j] = true 。 示例 nums = [1, 6, 11, 5] ： S = 23, target = 11 初始： dp = [true, false, ..., false] 处理 num=1 ： dp[1] = true 处理 num=6 ： dp[7] = true （因 dp[1] 为真） 处理 num=11 ： dp[11] = true （因 dp[0] 为真） 处理 num=5 ： dp[5] = true ， dp[6] = true （因 dp[1] 为真）， dp[10] = true （因 dp[5] 为真）等。 步骤 4：找最大可达和 从 j = target 向下找第一个 dp[j] = true 的 j ，本例中 j=11 可达。 最小差值 = |23 - 2*11| = 1 。 复杂度分析 时间复杂度：O(n × S)，其中 n 为数组长度，S 为总和。 空间复杂度：O(S)。 关键点 将最小划分问题转化为背包问题（容量 S/2，物品重量和价值均为 nums[ i ]）。 倒序更新避免重复选择同一数字。