最近刚开始学背包问题，做到了这个示例题。
问题分析
给定一个正整数数组 nums，判断是否能将其分割成两个和相等的子集。这个问题本质上等价于：是否存在一个子集，其元素和等于数组总和的一半。解决这个问题的关键在于将其转化为经典的 0-1背包问题。
二维动态规划解法
状态定义
定义二维数组 dp[i][j]，表示从数组前 i 个元素中选取若干元素，能否恰好凑出和为 j。最终目标是求 dp[n][sum/2] 是否为 true。
状态转移方程
- 不选第
i个元素：如果不选这个元素，那么剩下的元素是否可以刚好装满这个问题我们已经计算过:dp[i][j] = dp[i-1][j]（继承上一行的结果） - 选第
i个元素：如果要选这个元素，那么问题转换为使用0 到 i-1这些元素是否能刚好填满j-nums[i]这么大的空间。 如果j >= nums[i]，则dp[i][j] = dp[i-1][j - nums[i]]
最终结果为 dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]。
初始化
- 第一行（
i=0）：只有dp[0][nums[0]] = true，因为只能选择第一个元素。 - 第一列（
j=0）：dp[i][0] = true，表示不选任何元素时和为0。
示例演示
- 总和计算：1+5+9+5 = 20 → 目标值
target=10 - 初始化：
dp[0][0]=true,dp[0][1]=true
| i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | T | T | F | F | F | F | F | F | F | F | F |
| 1 | T | T | F | F | F | T | T | F | F | F | F |
| 2 | T | T | F | F | F | T | T | F | F | T | T |
| 3 | T | T | F | F | F | T | T | F | F | T | T |
当处理第三个元素 9 时，dp[2][10] 变为 true。说明使用更少元素的子问题已经可以完成目标，这个时候直接返回true即可。
一维动态规划优化
空间压缩原理
观察二维状态转移方程，发现 dp[i][j] 只依赖于 dp[i-1][...]。因此可以用一维数组 dp[j] 替代，通过 倒序遍历 避免覆盖上一行的结果。
状态转移方程
dp[j] = dp[j] || dp[j - nums[i]]（需从后向前更新）
代码解析
class Solution {
public boolean canPartition(int[] nums) {
// 计算总和并检查奇偶性
int sum = Arrays.stream(nums).sum();
if ((sum & 1) == 1) return false; // 总和为奇数时直接返回false
int target = sum >> 1; // 目标值为总和的一半
boolean[] dp = new boolean[target + 1]; // 一维DP数组
// 初始化：处理第一个元素
if (nums[0] <= target) {
dp[nums[0]] = true; // 只有nums[0]能恰好填满对应容量
}
int curSum = nums[0]; // 记录当前累计和，用于剪枝
for (int i = 1; i < nums.length; i++) {
if (nums[i] == target) return true; // 剪枝：当前元素等于目标值
curSum += nums[i];
// 确定遍历的起始点：不超过当前累计和或目标值
int start = Math.min(curSum, target);
// 倒序遍历，避免覆盖
for (int j = start; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]]; // 选或不选当前元素
}
// 剪枝： 如果使用更少的元素已经可以达成目标，则直接返回。
if (dp[target]) {
return true;
}
}
// 如果可以的话，循环内就会直接返回true。
return false;
}
}
关键优化点
- 倒序遍历：保证每个元素只被使用一次。
- curSum剪枝：限制遍历范围为
[nums[i], min(curSum, target)]，减少无效计算。 - 提前终止条件：当某个元素等于 sum/2 时直接返回
true。
复杂度分析
- 时间复杂度：O(n * sum)，其中
n为数组长度，sum为数组元素和。 - 空间复杂度：O(sum)，优化后仅需一维数组。