动态规划把重复出现的子问题保存下来，按照依赖关系求值。关键在于状态必须同时做到两件事：保留决定后续答案所需的信息，把不影响未来的历史舍去。先想清状态含义，再写转移，能避免“数组长度对了但问题解错”的情况。
0/1背包的状态是什么
每件物品有正整数重量和一个价值，最多拿一次，总重量不能超过容量。定义 dp[c] 为处理完当前这些物品后、容量不超过 c 的最大价值。初始全为零表示可以什么也不拿，因此负价值物品不会被强制选择。
处理重量 w、价值 v 的新物品时，最优解要么不拿它，保留旧值；要么拿它，并把剩余容量交给前面的物品。二维写法是 F[i][c]=max(F[i-1][c],F[i-1][c-w]+v)，后者仅在 c>=w 时存在。
def knapsack(items, capacity):
if capacity < 0 or any(weight <= 0 for weight, _ in items):
raise ValueError('capacity must be non-negative and weights positive')
dp = [0] * (capacity + 1)
for weight, value in items:
for current in range(capacity, weight - 1, -1):
dp[current] = max(dp[current], dp[current - weight] + value)
return dp[capacity]
if __name__ == '__main__':
print(knapsack([(2, 4), (3, 5), (4, 7)], 5))
一维优化要从大容量向小容量更新，使 dp[c-w] 仍来自上一轮。若反过来从小到大，同一件物品刚贡献的值会被再次使用：只有一件重量2、价值3的物品，容量4会错误得到6，而0/1背包应为3。完全背包允许重复拿，才可以使用相应的正向更新规则。
边界与复杂度
本例容量为5，物品 (2,4)、(3,5)、(4,7)，最优值9。时间 O(nW)，空间 O(W)。W是数值容量，输入只需 O(log W) 位表示它，所以这是伪多项式复杂度，容量极大时不能视为“对输入长度的多项式算法”。小件数场景也许适合折半搜索，价值较小时可以改变状态维度。
若要求重量恰好等于容量，除零容量外不能初始化为零，否则不存在的状态会被误认为可达。可以用负无穷表示不可达，再在转移时检查。若允许零重量，循环与取用次数需要另外讨论；示例明确要求正重量。
其他状态模型
最长公共子序列可用两个前缀长度作为状态：末字符相同则取左上角加一，否则取去掉一侧末字符后的较大值。编辑距离则把删除、插入、替换写成三种最后一步。区间DP用区间端点表达剩余子问题，树形DP按子树合并，DAG上的路径也可按拓扑顺序求解。
记忆化从需要的状态出发，方便跳过不可达部分；迭代表格显式确定依赖顺序，便于控制栈与内存。两者求解的是同一依赖图，不应仅凭递归或循环区分是否属于DP。
如何恢复方案
只存一维最优值会丢失历史选择。需要返回物品下标时，可保留二维表，从 F[n][W] 逆推：若值与上一行相同可以跳过当前物品，否则记录当前物品并扣除重量。存在多个最优解时先规定同分选择，才能写稳定的测试。
练习与面试自查
实现“恰好装满”的版本，加入容量不可达、空物品、负价值与单件不能重复的测试。再实现二维恢复，用返回下标重新计算重量和价值，检查每个下标只出现一次。面试应能讲清状态、初始条件、转移依赖、遍历顺序与复杂度，而不是只写出 max。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。