线性动态规划：分割等和子集（Partition Equal Subset Sum） 题目描述 给定一个只包含正整数的非空数组 nums ，判断是否可以将该数组分割成两个子集，使得两个子集的元素和相等。 示例 ： 输入： nums = [1, 5, 11, 5] 输出： true 解释：数组可以分割为 [1, 5, 5] 和 [11] ，两者和均为 11。 约束条件 ： 1 <= nums.length <= 200 1 <= nums[i] <= 100 解题思路 问题转化 ： 若两个子集和相等，则每个子集的和必须为整个数组和的一半。设总和为 S ，若 S 为奇数，直接返回 false （无法平分）。目标转化为：是否存在子集，其和为 target = S / 2 。 动态规划定义 ： 定义 dp[i][j] 表示前 i 个数字中是否存在子集和为 j 。 状态转移： 不选第 i 个数字： dp[i][j] = dp[i-1][j] 选第 i 个数字：若 j >= nums[i-1] ，则 dp[i][j] = dp[i-1][j - nums[i-1]] 两者取逻辑或（只要一种情况为真即可）。 初始条件： dp[0][0] = true （前 0 个数字和为 0 的情况存在），其他 dp[0][j] = false 。 优化空间 ： 由于 dp[i] 只依赖 dp[i-1] ，可压缩为一维数组 dp[j] ，从后向前遍历避免覆盖。 详细步骤 步骤 1：计算总和 S = sum(nums) ，若 S 为奇数则返回 false 。 target = S // 2 。 步骤 2：初始化 DP 数组 创建一维布尔数组 dp ，长度为 target + 1 。 dp[0] = true （和为 0 总是可达），其余初始为 false 。 步骤 3：状态转移 遍历每个数字 num ，从 target 反向遍历到 num ： dp[j] = dp[j] || dp[j - num] 。 步骤 4：返回结果 最终 dp[target] 即为答案。 示例推导（nums = [ 1, 5, 11, 5 ]） 总和 S = 22 ， target = 11 。 初始化 dp = [True, False, False, ..., False] （长度 12）。 遍历过程： num = 1 ：更新 j=11..1 ， dp[1] = True 。 num = 5 ：更新 j=11..5 ， dp[6] = True （因 dp[1] 为真）， dp[5] = True 。 num = 11 ：更新 j=11 ， dp[11] = True （因 dp[0] 为真）。 此时 dp[11] 为 true ，返回 true 。 关键点 问题本质是 0-1 背包问题 的变种，目标为恰好装满 target 。 反向遍历避免同一数字被重复使用（每个数字只能用一次）。 时间复杂度：O(n × target)，空间复杂度：O(target)。 通过以上分析，你可以理解如何将原问题转化为背包问题，并利用动态规划高效求解。