背包 DP，从不会到独立解题

从“选或不选”到第一张 DP 表

能亲手推导一个状态，并独立写出二维 01 背包。今天先不要求背一维模板。

1. 10 min准备建立 knapsack.cpp；画出物品表，口述“每件最多一次”。
2. 25 min理解看下面状态定义与两个分支，自己解释为什么只依赖上一行。
3. 20 min手推逐格填写容量 0…4 的表；再用单物品反例检查正序循环。
4. 25 min编码先写二维版，跑三组边界；有余力再改一维。
5. 10 min闭卷关掉代码，写出状态、转移、初始化，完成校验。

今天要理解的内容

1. 背包题先找三件事：可选物品、资源上限、要优化或统计的目标。物品不一定真是物品，也可能是数字、硬币或字符串。
2. 设 f[i][c] 为“只从前 i 件物品中选，总重量不超过 c 时的最大价值”。注意“不超过”允许空集合，和“恰好装满”不同。
3. 不选第 i 件：f[i-1][c]；能装下时选它：f[i-1][c-w[i-1]]+v[i-1]。取两者较大值。两条分支都只看前 i-1 件，因此不会重复选。
4. 这里重量为正、价值非负，f[0][c]=0，容量为 0 的最优值也是 0。时间 O(nW)，二维空间 O(nW)。
5. 压缩成 dp[c] 后要让 dp[c-w] 仍是上一轮的值，所以容量倒序。它是由依赖关系推出来的规则。

先在纸上跑一遍

物品 (重量,价值)：(1,15)、(3,20)、(4,30)，容量 4。

先遮住后面三行自己填。只有一件 (2,3)、容量 4 时答案是 3；一维正序却会得到 6，这是重复取物品的直接证据。

// C++17；w.size() == v.size()；重量 > 0，价值 >= 0
#include <algorithm>
#include <vector>
using namespace std;
int knapsack(const vector<int>& w, const vector<int>& v, int W) {
    int n = static_cast<int>(w.size());
    vector<vector<int>> f(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int c = 0; c <= W; ++c) {
            f[i][c] = f[i - 1][c];
            if (c >= w[i - 1])
                f[i][c] = max(f[i][c], f[i - 1][c - w[i - 1]] + v[i - 1]);
        }
    }
    return f[n][W];
}
// 一维：for (int c = W; c >= w[i]; --c)
//           dp[c] = max(dp[c], dp[c-w[i]] + v[i]);

即时校验 · 不看上文作答

选做 +20–30 分钟：把二维改成一维，并比较每轮结果一致；不追加新题。

把“能否分成两半”翻译成容量

看到非连续的子集选择，能把“等和划分”转成“恰好凑到 sum/2”。

1. 10 min复习白纸复述昨天的两个分支和倒序理由。
2. 20 min建模推导两组和相等意味着一组和为总和一半；先检查奇偶。
3. 15 min手推用 [1,2,5] 填容量 0…4 的可达状态。
4. 35 min实作做 LC 416；先写状态和初始化再写循环。
5. 10 min校验测奇数总和、不能划分、可划分；口述复杂度。

今天要理解的内容

1. 题目不是要求连续区间，而是每个数选或不选，恰好是一件物品最多使用一次。
2. 总和 S 为奇数直接 false。否则 T=S/2；问是否有子集和恰好等于 T。
3. 定义 dp[c]：处理完目前这些数后，是否存在子集恰好凑出 c。空集合能凑出 0，所以 dp[0]=true，其他为 false。
4. 转移 dp[c] = dp[c] || dp[c-x]，容量从 T 降到 x。逻辑或保留“不选”和“选”两种可行性。
5. 复杂度 O(nT)、空间 O(T)；它依赖数值大小，是伪多项式算法。不要看到 n 小就忽略 T 可能很大。

先在纸上跑一遍

[1,2,5] 总和 8，目标 4。处理 1 后可达 {0,1}；处理 2 后 {0,1,2,3}；5 超过目标，无法得到 4，答案 false。

#include <numeric>
#include <vector>
using namespace std;
bool canPartition(const vector<int>& nums) {
    int s = accumulate(nums.begin(), nums.end(), 0); // LC416 的范围下安全
    if (s % 2) return false;
    int t = s / 2;
    vector<char> dp(t + 1, false);
    dp[0] = true;
    for (int x : nums)
        for (int c = t; c >= x; --c)
            dp[c] = dp[c] || dp[c - x];
    return dp[t];
}

即时校验 · 不看上文作答

选做 +20–30 分钟：把代码改回二维布尔 DP；解释它和昨天最大价值表的相同点与不同点。

把差值最小转成装得尽量满

能从 S−2x 推出只需在 S/2 内寻找最大的子集和。

1. 10 min复习闭卷写 LC416 的状态、初始化、循环。
2. 20 min推导从两堆重量的差推导 S−2x，解释 x≤S/2。
3. 15 min手推对 [2,7,4,1,8,1] 找不超过 11 的可达和。
4. 35 min实作完成 LC1049，优先复用昨天的布尔思路。
5. 10 min校验检查单石头、完全平分、奇数总和。

今天要理解的内容

1. 两块石头相撞相当于重量做差。沿过程展开，每块原石头最终带一个正号或负号，所以关联到把重量分成两堆。
2. 设两堆总重为 x 和 S-x，令 x 是较小的一堆，则差为 S-2x。要差最小，就在 x≤⌊S/2⌋ 内尽量增大 x。
3. 从最小差划分出发，不断让两组的石头相撞。若最优差为 d，一组清空后另一组仍有多块，取一块残石 r，则 0＜r＜d。翻转组成这块残石的所有原石的正负归属，可得到差 |d−2r|＜d 的划分，与最优性矛盾。因此最小划分差能由碰撞实现。
4. 可以直接做子集可达 DP，再从 S/2 向下找第一个可达值。也可以把每块石头的重量同时作为“重量”和“价值”，做最大值背包。
5. 题目问最小差，不代表转移必须写 min；通过代数变换，核心反而是在半容量内做 max。

先在纸上跑一遍

[2,7,4,1,8,1]：S=23，半容量 11。可以选择 7+4=11，另一组重 12，最小差为 1。单石头 [7] 时容量 3 内只能选空集，答案 7。

#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
int lastStoneWeightII(const vector<int>& a) {
    int s = accumulate(a.begin(), a.end(), 0), t = s / 2;
    vector<int> dp(t + 1, 0); // 不超过 c 的最大可选重量
    for (int x : a)
        for (int c = t; c >= x; --c)
            dp[c] = max(dp[c], dp[c - x] + x);
    return s - 2 * dp[t];
}

即时校验 · 不看上文作答

选做 +20–30 分钟：给布尔版和 max 版做随机小数组对照，或解释为什么贪心“每次选当前最大石头”不能替代本题 DP。

从“有没有”走向“有几种”

能推导符号分配问题，分清布尔 OR 和方案数相加，并正确处理 0。

1. 10 min复习重讲昨天的代数建模；默写 01 循环。
2. 20 min推导写 P+N=S、P−N=target，解出 P。
3. 15 min手推手列 [0,0,1] 达到 target=1 的符号方案。
4. 35 min实作完成 LC494，专门测试零和不可能目标。
5. 10 min校验闭卷解释 dp[0]=1，而不是 0；记录错因。

今天要理解的内容

1. 把取正号的数归到 P、负号的数归到 N：P+N=S，P−N=target，因此 P=(S+target)/2。
2. 先检查 |target|≤S，再检查 S+target 是偶数。否则直接 0。原题数字非负，这个变换才可以直接用下面的数组背包。
3. dp[c] 表示恰好组成 c 的子集个数。dp[0]=1 是空集合的一种选择，其他为 0。每个位置都是不同物品，即使数值相同。
4. 把布尔题的 OR 换成加法：dp[c]+=dp[c-x]，仍然倒序。遇到 x=0 时，包括 c=0 在内的每一格会翻倍，代表 +0 和 -0。
5. 本题 n≤20，方案数最多 2^20，int 足够；通用计数题要依据约束选类型或取模。不能默认 long long 对任何计数都够用。

先在纸上跑一遍

[0,0,1]，target=1：(+0,+0,+1)、(+0,-0,+1)、(-0,+0,+1)、(-0,-0,+1)，共 4 种。处理一个 0 后 dp[0] 从 1 变 2，再处理一个 0 变 4。

#include <cstdlib>
#include <numeric>
#include <vector>
using namespace std;
int findTargetSumWays(const vector<int>& nums, int target) {
    int s = accumulate(nums.begin(), nums.end(), 0);
    if (abs(target) > s || (s + target) % 2) return 0;
    int t = (s + target) / 2;
    vector<int> dp(t + 1, 0);
    dp[0] = 1;
    for (int x : nums)
        for (int c = t; c >= x; --c) // 用有符号 int；x 可为 0
            dp[c] += dp[c - x];
    return dp[t];
}

即时校验 · 不看上文作答

选做 +20–30 分钟：对 n≤10 的数组枚举全部正负号，与 DP 比较；这也是 C++ 实践中验证算法的好习惯。

允许重复取：先解决最少硬币

能解释正序如何允许重复使用，并区分不可达状态与最优值 0。

1. 10 min复习用一件 (2,3) 比较 01 与无限使用的不同结果。
2. 20 min理解推导最少硬币的状态、INF 和正序依赖。
3. 15 min手推coins=[1,3,4]、amount=6，填出金额 0…6。
4. 35 min实作完成 LC322；用 [2],3 验证不可达分支。
5. 10 min校验默写最小值初始化并解释为什么不能全 0。

今天要理解的内容

1. 每种硬币可以用无限次，选择一枚 x 后还可以继续选择 x。原题硬币面值为正；零面值或负面值不能直接套这个模型。
2. dp[c] 为恰好凑出金额 c 所需的最少硬币数。dp[0]=0，其他设为 INF，表示还不可达。
3. 硬币在外、金额正序：dp[c]=min(dp[c],dp[c-x]+1)。此时 dp[c-x] 可以包含本轮这枚硬币，从而允许重复取。
4. 取 INF=amount+1 就足够：正整数硬币凑出 amount，任何可行方案的硬币数不会超过 amount。避免直接给 INT_MAX 后再 +1。
5. 金额在外、枚举最后一枚硬币，也能求最少个数。两种循环顺序都能用于这里的 min，但计数题的顺序会影响答案，明天专门比较。

先在纸上跑一遍

coins=[1,3,4]，dp[0…6] 的最终值是 [0,1,2,1,1,2,2]。6=3+3 只需两枚；贪心先拿 4 再拿 1、1 得到三枚，不是最优。

#include <algorithm>
#include <vector>
using namespace std;
int coinChange(const vector<int>& coins, int amount) {
    const int INF = amount + 1;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int x : coins)
        for (int c = x; c <= amount; ++c)
            dp[c] = min(dp[c], dp[c - x] + 1);
    return dp[amount] == INF ? -1 : dp[amount];
}

即时校验 · 不看上文作答

选做 +20–30 分钟：LC 279 · 完全平方数 ↗ 只做建模：把不大于 n 的正平方数当硬币，先不强制再写一题。

组合与排列：循环在数什么

能用 {1,2}、目标 3 的例子解释外层循环的语义，而不只记口诀。

1. 10 min复习复述 494 的计数初始化与 322 的正序理由。
2. 20 min理解比较“按硬币种类构建组合”和“按最后一步构建序列”。
3. 15 min手推列出 {1,2} 凑 3 的组合与有序序列。
4. 35 min实作主做 LC518；把外层换成金额后观察结果。
5. 10 min校验给同伴或自己解释 1+2 与 2+1 是否同一种。

今天要理解的内容

1. 今天仍然是 dp[0]=1 的计数，但必须先问：选取顺序不同算不算不同方案？
2. 组合不计顺序：硬币外层、金额正序。处理到某种硬币时，只使用已经处理过的种类，所以一个多重集合只按固定种类顺序被构建一次。
3. 排列计顺序：金额外层、数字内层。把 x 当作序列最后一个数，每种最后一步对应一组独立序列。必须所有数字为正，才按金额形成无环依赖。
4. 01/完全决定同物品是否能复用；组合/排列决定是否区分顺序。这是两个不同问题，不要混为一个口诀。
5. 计数可能溢出。下面 LC518 参考版使用饱和加法保护中间状态：原题保证最终答案不超过 INT_MAX，非负加法构成的状态可以截断到该上界，最终有界结果仍保持精确。练习小样例可用 long long；泛化到别的题需重新检查。

先在纸上跑一遍

硬币 {1,2} 凑金额 3：组合是 {1,1,1}、{1,2}，共 2；有序序列是 [1,1,1]、[1,2]、[2,1]，共 3。先枚举再跑两种循环，不能只比较代码长相。

#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
int change(int amount, const vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int x : coins) // 种类在外：不计顺序
        for (int c = x; c <= amount; ++c)
            dp[c] = static_cast<int>(min<long long>(
                INT_MAX, 1LL * dp[c] + dp[c - x]));
    return dp[amount];
}
// 小范围有序计数（另需验证答案和中间值范围）：
// for (int c = 1; c <= amount; ++c)
//     for (int x : coins)
//         if (c >= x) dp[c] += dp[c-x];

即时校验 · 不看上文作答

选做 +20–30 分钟：可选完成 LC377；如果采用 int 直接累加，要先核对题目范围，避免中间求和溢出。

两个容量，还是同一个选或不选

能从一个字符串同时消耗 0 和 1，推导二维容量状态与双倒序。

1. 10 min复习默写一维 01 最大值背包；解释容量维度与物品维度。
2. 20 min建模每个字符串当一件物品；重量变成 (零个数,一个数)，价值为 1。
3. 15 min手推用 ["10","0","1"]、m=1,n=1 比较选一件和选两件。
4. 35 min实作用 25 分钟完成 LC474，10 分钟把每个字符串的价值从 1 改为给定 reward，检查两个容量都倒序。
5. 10 min校验用只含 0 或只含 1 的字符串检查循环边界。

今天要理解的内容

1. 二维容量不是“二维 DP 就更难”：只是同一次选择同时消耗两个资源，依然分为选当前字符串或不选。
2. dp[z][o] 表示零的预算不超过 z、壹的预算不超过 o 时最多选多少个字符串。预算允许剩余，因此全 0 初始化。
3. 当前字符串有 a 个 0、b 个 1，转移为 max(dp[z][o], dp[z-a][o-b]+1)。这件物品只能用一次。
4. 两个容量都倒序是最稳妥的实现。尤其字符串可能只含一种字符，一个资源消耗可能为 0，不能想当然忽略另一维循环方向。
5. 时间 O(L+kmn)，L 是所有字符串长度之和，k 是字符串数；空间 O(mn)。若把物品维度也保留，则是三维状态。

先在纸上跑一遍

["10","0","1"]、m=1,n=1：选 "10" 只能得到 1 件；选 "0" 与 "1" 能得到 2 件。只有 ["0"]、m=2,n=0 时最多是 1 件，若算出 2 就重复使用了同一字符串。

加权小变式：字符串 ["0","1","01"] 的收益分别为 [2,3,8]，预算 (1,1)，最大收益为 8。只需把转移中的 +1 换成 +reward[i]；目标从“数量最多”变为“收益最大”。这一步为周日任务调度题做准备。

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int findMaxForm(const vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const string& s : strs) {
        int a = static_cast<int>(count(s.begin(), s.end(), '0'));
        int b = static_cast<int>(s.size()) - a;
        for (int z = m; z >= a; --z)
            for (int o = n; o >= b; --o)
                dp[z][o] = max(dp[z][o], dp[z - a][o - b] + 1);
    }
    return dp[m][n];
}

即时校验 · 不看上文作答

选做 +20–30 分钟：只了解：多重背包是每种物品有次数上限；分组背包是每组最多选一个。它们是后续课程，不计入这次达标要求。

撤掉题型标签，完成一次独立解题

把题意翻译成状态的过程变成自己的能力，为明天留出体力。

1. 10 min热身闭卷写“每件几次、恰好/不超过、求什么、顺序是否区分”。
2. 20 min复练 A不看历史代码重做 LC416，先口述再编码。
3. 20 min复练 B不看历史代码重做 LC322，测不可达和零金额。
4. 20 min复练 CLC494、518、474 中选之前最弱的一题重写。
5. 20 min复盘按错因定位到状态/初始化/转移/顺序/边界；只修一个最弱点。

今天要理解的内容

1. 在敲循环前先写一句完整状态定义：“处理到哪里，用多少资源，dp 存的到底是什么”。不要只写“dp 是最优解”。
2. 接着写出空集合和不可达状态：最大值且不超过容量通常全 0；可达性只有 dp[0]=true；方案计数 dp[0]=1；最少数量 dp[0]=0、其余 INF。
3. 从原始状态依赖推循环：01 取上一轮所以倒序；无限复用可取本轮所以正序；计数还必须先判断顺序语义。
4. 每道题至少准备三个检查：最小输入、无法达成、能暴露重复使用或顺序计数的反例。先能解释，再求一次 AC。
5. 今天不新增困难题、不预看明天参考解。多重背包、分组背包、单调队列优化、状压 DP 放到下一阶段。

先在纸上跑一遍

拿到任何新题，先填这张卡：物品＝___；资源＝___；每件次数＝___；目标＝___；顺序算不同吗＝___；dp 定义＝___；初值＝___；转移＝___；遍历＝___；复杂度＝___。

// 独立解题前的文字检查卡（不需要背诵一段万能代码）：
// 1. 物品是否能重复？数字可能为 0/负数吗？
// 2. 容量是恰好达到，还是不超过？
// 3. dp 表示 bool / max / min / count 中的哪一种？
// 4. 计数是否区分顺序？值相同的位置是否算不同物品？
// 5. 初始化、依赖的轮次、最终读取哪个状态？
// 6. 时间空间是否匹配范围？加法或 INF 会不会溢出？

即时校验 · 不看上文作答

选做 +20–30 分钟：最多追加 20 分钟：把最弱题关掉答案再写一遍。不要把可选时长变成追赶新题的负担。