背包 DP 的状态设计：先问“最后一步”

用最后一步的选择组织状态和转移，并梳理 0/1 背包中循环顺序背后的因果关系。

更新于 2026年9月22日约 1 分钟阅读

状态不是凭空定义的

设计 DP 时，先问最优解的最后一步做了什么。对 0/1 背包而言，最后一个物品只有选或不选。

定义 $f[i][j]$ 表示只考虑前 $i$ 个物品、容量不超过 $j$ 时的最大价值：

$f[i][j]=\max(f[i-1][j], f[i-1][j-w_i]+v_i)$

压缩第一维后，倒序枚举容量可以保证右侧仍是上一层状态。正序会让同一个物品被重复使用，问题就悄悄变成了完全背包。

for (int i = 1; i <= n; ++i)
  for (int j = capacity; j >= weight[i]; --j)
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

循环顺序不是模板习惯，而是状态依赖的拓扑序。