数据结构与算法 / 系统课时
建立面试竞赛解题检查清单
建立面试竞赛解题检查清单
动态规划现场失分往往不是完全不会,而是状态少一维、初始化漏一种情况、遍历方向写反或答案取错位置。把这些高频错误固定成一套检查顺序,可以在有限时间内更稳定地完成建模、编码和自测。
学习目标
- 用固定顺序完成题型判断、状态设计、转移和边界检查
- 根据状态依赖关系确定正确遍历顺序与答案位置
- 在超时或结果异常时快速定位模型、实现或优化层面的错误
先用八个问题完成建模
拿到一道疑似动态规划的题,不必立刻写 dp 数组。先依次回答下面八个问题,能够明显减少写到一半推翻模型的概率。
- 题型判断:是否存在大量重复子问题,并且大问题能由规模更小的子问题组合得到?
- 状态定义:
dp[...]中每一维具体代表什么,状态值表示最优值、可行性还是方案数? - 转移来源:当前状态能够由哪些更小状态到达,每个来源需要满足什么条件?
- 初始条件:最小规模问题的真实答案是什么,哪些状态不可达?
- 遍历顺序:计算当前状态之前,它依赖的状态是否已经计算完成?
- 答案位置:最终答案一定在最后一个状态,还是需要对一组状态再取最优值或求和?
- 复杂度:状态数量乘以单个状态的转移成本是否能通过数据规模?
- 优化空间:是否只依赖前一层、固定窗口或有限状态,从而可以压缩空间?
其中最重要的一条是:先用一句完整的话定义状态,再写转移式。 如果无法准确说出 dp[i][j] 代表什么,后面的初始化和循环通常也无法稳定确定。
让遍历顺序服从依赖关系
很多错误代码的转移公式本身没有问题,真正出错的是状态被提前覆盖。0/1 背包的一维优化就是典型例子:每件物品只能使用一次,因此更新容量时必须从大到小遍历。
下面同时运行正向和逆向两种写法。正向更新会在处理同一件物品时再次读取本轮刚更新的状态,相当于允许一件物品被重复选择。
def knapsack_forward(weights: list[int], values: list[int], capacity: int) -> int:
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# 错误示范:正向更新会重复使用当前物品。
for c in range(w, capacity + 1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
def knapsack_backward(weights: list[int], values: list[int], capacity: int) -> int:
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# 逆向更新保证 dp[c - w] 仍来自上一轮物品集合。
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
weights = [2]
values = [3]
capacity = 4
print("forward:", knapsack_forward(weights, values, capacity))
print("backward:", knapsack_backward(weights, values, capacity))预期输出
forward: 6
backward: 3只有一件重量为 2、价值为 3 的物品,0/1 背包显然不能得到价值 6。这个反例说明,检查遍历顺序时不能只问“循环能不能覆盖所有状态”,还必须问“读取的是上一阶段状态,还是本阶段刚写入的状态”。
编码后按固定顺序自测
代码完成后,优先使用能够击中边界的小样例,而不是直接构造复杂随机数据。先检查空输入或最小规模,再检查必须选、一定不能选、多个方案并列,以及状态边界恰好被取到的情况。
随后重新定位答案。如果状态表示“前 i 个元素的最优值”,答案可能是 dp[n];如果状态还保留最后位置、剩余容量、结束状态等维度,答案可能需要在多个末态中再次取最大值或求和。很多“样例差一点”的错误都来自这里。
最后估算复杂度。设状态数量为 ,平均每个状态枚举 个来源,通常可以先按 估算时间。若数量级明显超过题目允许范围,应先寻找减少状态或加速转移的方法,而不是依赖常数优化侥幸通过。
错答和超时时从不同入口回滚
结果错误时,建议逆着实现链检查:先看答案位置,再查遍历顺序、边界和初始化,之后才重新怀疑状态定义与转移。因为越靠近代码末端的问题修复成本越低,没有必要每次都从头重做模型。
超时时则从复杂度入口检查。先确认状态数量是否过大,再看每个状态是否包含额外枚举;如果模型复杂度本身已经满足要求,才继续检查重复计算、低效容器或不必要的状态存储。
如果出现“加空间优化前正确,压缩后错误”,应优先恢复未压缩版本,对照依赖方向重新判断哪些旧状态必须保留。空间优化不是独立技巧,它只是对已经确认正确的依赖关系进行存储复用。
把检查清单变成现场动作
真正上场时,可以把整套流程压缩成一句顺序:判题型,定义状态,列来源,定初值,看依赖,找答案,算复杂度,最后优化。 每完成一步再进入下一步,可以显著减少一边写代码一边修改状态含义的情况。
这份清单的价值不在于让所有动态规划题变得机械,而在于把最容易遗漏、又能够系统检查的问题固定下来。遇到陌生题时仍然需要建模能力,但一旦模型形成,就能用同一套检查顺序把它可靠地落实为代码。