dp[i][j] = dp[i-1][j] || (j >= nums[i-1] ? dp[i-1][j - nums[i-1]] : false)

dp[j] = dp[j] || dp[j - nums[i]]

我来给你讲解 LeetCode 第 416 题「分割等和子集」 。 题目描述 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1： 输入：nums = [ 1,5,11,5 ] 输出：true 解释：数组可以分割成 [ 1, 5, 5] 和 [ 11 ]，它们的和都是 11。 示例 2： 输入：nums = [ 1,2,3,5 ] 输出：false 解释：数组不能分割成两个和相等的子集。 思路分析 第一步：问题转化 如果数组总和是奇数，那么不可能分成两个和相等的子集（因为和相等意味着总和必须是偶数）。 如果总和是偶数，设总和为 sum ，那么问题转化为： 能否从数组中选出一些数，使它们的和等于 sum/2 。 这样，问题就变成了一个 子集和问题 ，即 0-1 背包问题 的变种。 第二步：定义状态 我们可以用动态规划来解决。 定义 dp[i][j] 为：考虑前 i 个数字，能否选出一些数，使它们的和等于 j 。 i 的范围：0 到 n（n 是数组长度） j 的范围：0 到 target （ target = sum/2 ） 最终答案是 dp[n][target] 。 第三步：状态转移 对于第 i 个数（数值为 nums[i-1] ，因为 i 从 1 开始计数）： 如果不选这个数： dp[i][j] = dp[i-1][j] 如果选这个数：需要 j >= nums[i-1] ，并且 dp[i][j] = dp[i-1][j - nums[i-1]] 所以： 第四步：初始化 dp[0][0] = true ：考虑 0 个数，和为 0，是可以的（不选任何数）。 对于 j > 0 ， dp[0][j] = false ：没有数字可选，和不可能大于 0。 第五步：空间优化 观察状态转移方程， dp[i][j] 只依赖于 dp[i-1][...] ，所以可以优化为一维数组： dp[j] 表示：能否用已考虑的数字凑出和 j 。 遍历顺序： 外层循环遍历每个数字 内层循环从 target 到 nums[i] 倒序遍历（防止一个数字被重复使用） 转移方程： 初始条件： dp[0] = true ，其余为 false。 第六步：代码逻辑 计算总和，如果是奇数，返回 false。 设 target = sum / 2 。 初始化 dp 数组，长度为 target+1 ， dp[0]=true 。 遍历每个数字，内层从 target 到该数字倒序更新 dp 。 返回 dp[target] 。 举例说明 nums = [ 1,5,11,5 ] 总和 = 22，target = 11。 初始化 dp = [ true, false, false, ..., false ]（长度 12） 数字 1：更新 j=11 到 1 j=1: dp[ 1] = dp[ 1] || dp[ 0 ] → true 数字 5：更新 j=11 到 5 j=6: dp[ 6] = dp[ 6] || dp[ 1 ] → true j=5: dp[ 5] = dp[ 5] || dp[ 0 ] → true 数字 11：更新 j=11 到 11 j=11: dp[ 11] = dp[ 11] || dp[ 0 ] → true → 找到答案，返回 true 这样，我们就用 0-1 背包 的思路解决了这个问题，时间复杂度 O(n × target)，空间复杂度 O(target)。