DP 表像传送带：算一格只用到「上一行」，后面的行可以丢进回收站。表不用整张存——滚着算、原地覆盖，空间从 O(n×m) 降到 O(m) 甚至 O(1)，答案一分不少。
工厂的传送带上只放得下两个托盘：「上一排」和「当前排」。工人算当前排时只抬头看上一排——上一排用完后就滑进回收站（内存释放），新排写到同一块板上。DP 表就是这种传送带：只要算第 i 行最多用到第 i-1 行，整张表就可以换成「1~2 行」反复覆盖。斐波那契只依赖前两项 → 连 1 行都不用，2 个变量轮着用；0/1 背包、网格路径、LCS 都能滚。滚动的关键：覆盖的顺序不能把「还要用的旧值」碾掉——0/1 背包容量要倒着推（后面细说）。
// 逐个看转移式：算 dp[i][*] 会不会用到「更早的行」？ // 1) 斐波那契 f[i] = f[i-1] + f[i-2] → 只依赖前 2 项 → 能滚（滚到 2 个变量） // 2) 0/1 背包 dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]] + val[i]) // → 只用第 i-1 行（上一行）→ 能滚（1 行 → 一维数组） // 3) 网格路径 dp[i][j] = dp[i-1][j] + dp[i][j-1] // → 上一行 + 当前行左侧（刚算好的）→ 能滚（1 行，正推） // 4) LCS dp[i][j] 用到 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] // → 上一行、当前行左侧、对角（上一行前一列）→ 能滚（1 行 + 1 个临时变量） // 结论：算当前行「最多只用到上一行」→ 整张表可以换成 1~2 行反复覆盖 = 滚动数组。 // 若用到「上上行的更早行」（行差为 2），就要留 2 行轮着用； // 留几行 = 转移式引用的「最大行差」。 // 反例：区间 DP（合并石子）dp[i][j] 要用 dp[i][k] 和 dp[k+1][j]—— // 这两个是「同一行里的更短区间」，不是「上一行」，一维简单滚不适用（进阶，先不纠结）。
// 斐波那契：f[1]=1, f[2]=1, f[i] = f[i-1] + f[i-2] // 全表版：int f[10005]; for (i=3..n) f[i]=f[i-1]+f[i-2]; 空间 O(n) // 滚动版：只留 2 个变量——a = 前一项，b = 前前项 int a = 1, b = 1; // a = f[2]，b = f[1] if (n == 1 || n == 2) { cout << 1; return 0; } int c; for (int i = 3; i <= n; i++) { c = a + b; // 新值 = 前一项 + 前前项 b = a; // 「前前项」往前滑一步（先挪旧的） a = c; // 「前一项」滑到新位置 } cout << a; // 循环结束后 a 就是 f[n] // 手推 n = 6：起点 (a,b) = (1,1) // i=3: c=2 → (a,b) = (2,1) → f[3] = 2 // i=4: c=3 → (a,b) = (3,2) → f[4] = 3 // i=5: c=5 → (a,b) = (5,3) → f[5] = 5 // i=6: c=8 → (a,b) = (8,5) → f[6] = 8 ✓
// 二维回顾（六级）：dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]] + val[i]) // 一维滚动：用一个数组 f[v] 原地覆盖，公式形状不变： for (int i = 1; i <= n; i++) for (int v = V; v >= w[i]; v--) // 关键：v 从大到小（倒着推） f[v] = max(f[v], f[v - w[i]] + val[i]); // 手推演示：只有 1 件物品 A（w=2, val=3），容量 V=5，f 初始全 0 // —— 正推 v = 2 → 5（错）： v=2: f[2] = max(0, f[0]+3) = 3 // f[0] 是旧值 ✓ v=3: f[3] = max(0, f[1]+3) = 3 // f[1] 是旧值 ✓ v=4: f[4] = max(0, f[2]+3) = 6 // f[2] 刚被更新成 3（新值）→ A 被拿了 2 次 ✗ v=5: f[5] = max(0, f[3]+3) = 6 // f[3] 也是新值 → A 又拿了 2 次 ✗ // —— 倒推 v = 5 → 2（对）： v=5: f[5] = max(0, f[3]+3) = 3 // f[3] 还没轮到，仍是旧值 0 ✓ v=4: f[4] = max(0, f[2]+3) = 3 // f[2] 仍是旧值 0 ✓ v=3: f[3] = max(0, f[1]+3) = 3 v=2: f[2] = max(0, f[0]+3) = 3 // A 只拿 1 次 ✓ // 同一件物品：正推 →「无限次拿」（完全背包）；倒推 →「最多拿 1 次」（0/1 背包）。
// ① 网格路径（4×4 点阵，只能向右/向下）：dp[i][j] = dp[i-1][j] + dp[i][j-1] // 一维：f[j] = f[j] + f[j-1]，j 正推 1→m。这里「被覆盖的旧值」正是需要的上一行， // f[j-1] 新值正是当前行左侧——方向与 0/1 背包相反！ // 手推（f 初始 = 第 0 行 = [1,1,1,1]）： // 第 1 行：f[1]=1+1=2 → f[2]=1+2=3 → f[3]=1+3=4 → [1,2,3,4] // 第 2 行：f[1]=2+1=3 → f[2]=3+3=6 → f[3]=4+6=10 → [1,3,6,10] // 第 3 行：f[1]=3+1=4 → f[2]=6+4=10 → f[3]=10+10=20 → [1,4,10,20] // 答案 f[3] = 20 ✓（与二维表最后一格一致） // ② LCS 一维滚动：需要 上=旧f[j]、左=新f[j-1]、对角=旧f[j-1] // 旧 f[j-1] 会被新值碾掉 → 用变量 diag 提前存住（= 上一列的旧值） for (int i = 1; i <= n; i++) { int diag = 0; // 每行开头：第 0 列边界 = 0 for (int j = 1; j <= m; j++) { int old = f[j]; // 存住旧 f[j]（下一列的对角） if (A[i-1] == B[j-1]) f[j] = diag + 1; else f[j] = max(f[j], f[j-1]); // 旧 f[j]=上，f[j-1]=当前行左 diag = old; // 下一列的对角 = 本列旧值 } } // 手推 A="AB", B="BA"：初始 f=[0,0,0] // i=1('A')：j=1 不同 f[1]=max(0,0)=0；j=2 同 f[2]=0+1=1 → [0,0,1] // i=2('B')：j=1 同 f[1]=0+1=1；j=2 不同 f[2]=max(旧1, 左1)=1 → [0,1,1] // 答案 f[2] = 1 ✓（LCS("AB","BA") = 1）
// 0/1 背包（一维版）：n 件物品，背包容量 V，第 i 件重量 w[i]、价值 val[i]， // 每件最多拿 1 件，求能装下的最大总价值。空间 O(V)（六级二维版是 O(n×V)）。 #include <iostream> #include <algorithm> using namespace std; int w[1005], val[1005], f[10005]; // f[v]：容量 v 能达到的最大价值（一维，滚动） int main() { int n, V; cin >> n >> V; for (int i = 1; i <= n; i++) cin >> w[i] >> val[i]; for (int i = 1; i <= n; i++) for (int v = V; v >= w[i]; v--) // 倒推：0/1（每件最多一次） f[v] = max(f[v], f[v - w[i]] + val[i]); cout << f[V] << endl; return 0; } // 样例：n=2, V=5；物品 (2,3)、(3,4) → 输出 7（两件都拿，重量 5 价值 7） // 对照：内层若改正推（v = w[i]; v <= V; v++）→ 变成完全背包（物品可反复拿）。