9._分割等和子集(没懂（懂了）

$dp[j] = dp[j] || dp[j-num];$

• 2.19

  • 数组为 target 的 boolean 数组，代表是否能找到目标数
  • 外层物品内部背包

• 2.4

  • 01 背包问题dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);，不同于凑硬币的完全背包问题（能重复使用硬币）
  • 主要就是倒这走

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int target = sum/2;
 
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for(int num:nums){
            for(int j=target;j>=num;j--){
                dp[j] = dp[j]||dp[j-num];
            }
        }
        return dp[target];
    }
}

• 12.6
  1. 没那么难，前面一大堆 i. 算 target，dp0 为 true
  2. 外层控制物品，内层控制背包

需要倒叙target到num boolean[] dp = new boolean[target + 1];

• 0-1背包问题,避免用到同一个num,num是正序的,j是倒叙的,倒叙

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num:nums) sum+=num;
        if(sum%2!=0) return false;
        int target = sum/2;
        boolean[] dp = new boolean[target+1];
        dp[0]=true;
        for(int num:nums){//外层控制物品
            for(int j=target;j>=num;j--){//内层循环的下标 j，表示“背包容量 / 当前目标和”。
                dp[j] = dp[j] || dp[j-num];
            }
        }
        return dp[target];
    }
}

• dp长度是target+1
• 记住状态转移方程吧,有点难

🧠 关键：防止「重复使用同一个数」

假设 nums = [2, 3], target = 5 初始状态： dp[0] = true dp[1..5] = false

j	5	4	3	2	1	0
旧dp	❌	❌	❌	✅	❌	✅
更新后	✅(2+3)	❌	✅	✅	❌	✅
好的，我们用你给的例子 [1, 5, 11, 5] 来人工跑一遍代码。这是一个非常好的例子，因为它能清晰地展示状态是如何累积的。

1. 准备工作

• 输入数组：nums = [1, 5, 11, 5]

• 计算总和：1 + 5 + 11 + 5 = 22

• 判断奇偶：22 是偶数，可以尝试拆分。

• 计算目标：target = 22 / 2 = 11。

• 初始化 DP 数组：大小为 12 (索引 0~11)。

  • dp[0] = true (凑出0总是可以的)

  • dp[1...11] = false (暂时都凑不出来)

---

2. 逐个数字推导 (DP 更新过程)

我们要遍历每个数字 num，然后倒着更新 dp 数组。

公式：dp[j] = dp[j] || dp[j - num]

第一轮：处理数字 1

• 内层循环 j 从 11 倒着遍历到 1。

• 关键变化：

  • 当 j = 1 时：dp[1] = dp[1] || dp[1-1] $\rightarrow$ false || dp[0] $\rightarrow$ True。

• 本轮结束后的 dp 状态：

  • dp[0], dp[1] 是 True。

  • 意味着我们现在能凑出的和有：0, 1。

第二轮：处理数字 5

• 内层循环 j 从 11 倒着遍历到 5。

• 关键变化：

  • 当 j = 6 时：dp[6] = dp[6] || dp[6-5] $\rightarrow$ false || dp[1] (上一轮算出的True) $\rightarrow$ True。

    • 解读：之前有 1，现在加 5，所以能凑出 6。

  • 当 j = 5 时：dp[5] = dp[5] || dp[5-5] $\rightarrow$ false || dp[0] $\rightarrow$ True。

    • 解读：之前有 0，现在加 5，所以能凑出 5。

• 本轮结束后的 dp 状态：

  • dp[0], dp[1], dp[5], dp[6] 是 True。

  • 意味着我们现在能凑出的和有：0, 1, 5, 6。

第三轮：处理数字 11

• 内层循环 j 从 11 倒着遍历到 11。

• 关键变化：

  • 当 j = 11 时：dp[11] = dp[11] || dp[11-11] $\rightarrow$ false || dp[0] $\rightarrow$ True。

• 本轮结束后的 dp 状态：

  • dp[11] 变成了 True。

  • 其实到这里，dp[target] 已经是 True 了，答案已经是 true 了。 但代码会继续跑完。

第四轮：处理最后一个数字 5

• 内层循环 j 从 11 倒着遍历到 5。

• 关键变化：

  • j = 11：dp[11] 已经是 True，保持不变。（或者通过 dp[11-5] = dp[6] (True) 再次确认 True）。

  • j = 10：dp[10] = dp[10] || dp[10-5] $\rightarrow$ false || dp[5] (True) $\rightarrow$ True。

    • 解读：之前有 5，再加这个 5，凑出 10。

  • j = 6：已经是 True。

  • j = 5：已经是 True。

• 最终状态：

  • 能凑出的和包括：0, 1, 5, 6, 10, 11 等。

3. 最终结果

函数返回 dp[11]，也就是 true。

总结变化表

轮次 (数字)	处理前能凑出的和 (True的下标)	本轮新增的能凑出的和	原理
初始	0	-	-
1	0	1	0 + 1 = 1
5	0, 1	5, 6	0+5=5, 1+5=6
11	0, 1, 5, 6	11, 12…	0+11=11 (1+11越界忽略)
5	0, 1, 5, 6, 11	10	5+5=10

最后 dp[11] 是亮的（True），说明能拆分！

拆分方案其实是：[11] 一组，[1, 5, 5] 一组。