动态规划填表动画演示
一格一格把子问题填出来，回溯就知道谁被选中。
键盘：← → 单步 ·空格 播放/暂停 · R 重置 ·Home/End 到两端
动态规划填表在这里就是一张二维格子：行是「考虑过前几件物品」，列是「容量还剩多少」，每格填的是这个子问题的最优值。填每一格只需要两次取数一次比较——不拿这一件（抄上一行同列）、拿这一件（抄上一行左边 w 格再加价值）。当前格亮着，抄来源那一格会一并点亮；填完从右下角沿来源往回走，就能把「到底哪几件被选中」读出来，最优值不再只是一个数。
四档题面的表形状各不相同：0/1 背包与完全背包的差别只在第二个候选取上一行还是本行左边，一行的差别决定了同一件物品能不能重复拿；爬楼梯压成一维，格子是「到第几阶有几种走法」；最长公共子序列行是串 A 的前缀、列是串 B 的前缀，字符相等时取左上角加一，回溯时也只在相等那一步收下字符。状态怎么定义，直接决定表长什么样、从哪几格取数。
动态规划填表演示怎么用
- 换题面：四档共用一个页面：0/1 背包、完全背包、爬楼梯、最长公共子序列。前两者可以拿同一份物品与容量各跑一遍，比较最优值。
- 改物品与容量：物品写「重/值」，逗号分隔，最多 6 件；容量上限 10。表格规模就是 (件数+1)×(容量+1)，改小一点更容易逐格核对。
- 盯来源格：每填一格都先标出被抄的那格；改成完全背包后再看，取的是同一行左边，这就是「同一件还能再来一次」的形状证据。
- 读回溯：末步给出最优值与被选中的物品、合计重量；LCS 那档把公共子序列逐字排在第三排格子里，长度写在旁边。
常见问题
0/1 背包用一维滚动数组，内层容量为什么要倒着推？
一维数组里 dp[j] 保存的是「上一行」还是「本行」的值，取决于你什么时候覆盖它。倒着推时 dp[j-w] 还没被本轮更新，读到的一定是上一行那一格，正好对应「这件最多拿一次」；正着推时 dp[j-w] 已经写过，本轮刚放进去的那件会被再拿一遍，同一件物品重复计入，代码悄悄变成了完全背包。
完全背包就该正着推吗？
对。完全背包允许同一件无限次拿，转移是 dp[j] = max(dp[j], dp[j-w] + v)，右边的 dp[j-w] 恰恰必须是「本轮已经考虑过这件」的值才合语义，所以内层要从小到大推。同一个方向规则也适用于凑零钱、爬楼梯这类「有序方案数」问题：外层物品、内层容量决定组合数，交换两层就变成排列数。
爬楼梯的 f[0] 为什么是 1 而不是 0？
f[i] 是「走到第 i 阶的走法数」，站在起点不动本身就是走完 0 阶的一种走法。f[0] 写成 0，那么 f[2] = f[1] + f[0] 就只剩 1，把「一步跨两阶」这条路径丢了。同理，凑零钱里 dp[0] = 1 表示「凑出 0 有且只有一种：什么都不选」，这些「空方案记 1」的初始值是递推的底座。
LCS 的回溯为什么只在相等那一步收下字符？
表格里 dp[i][j] 有三种来路：字符相等时来自左上角加一，不等时来自正上或正左的较大值。只有「左上角 +1」那一步意味着 A 的第 i-1 位与 B 的第 j-1 位真的配成了一对，回溯走到这里才把字符收下；其余情况只是把已经求出的长度沿行或列平移过去，收下就会造出一个并非公共子序列的串。
背包的 O(nW) 为什么叫伪多项式？
代价里的 W 是容量的数值，而不是输入的长度。把容量写成二进制需要 log W 位，所以时间相对输入规模其实是指数级的。这也是背包能用动态规划做、却没有「多项式解」的原因：容量特别大时该考虑价值维度的 DP 或近似算法，而不是硬填这张表。