数据结构与算法 / 系统课时
定位状态定义与边界类错误
定位状态定义与边界类错误
动态规划出现错误答案时,最容易被忽略的往往不是转移式,而是状态含义和边界条件。这里用一套固定排查顺序,把定义、初值、非法状态、循环范围和答案位置逐层拆开,并用最小反例快速定位第一处错误。
学习目标
- 能把
dp中每个下标重新翻译成一句精确的人话,并据此检查转移是否匹配。 - 能系统核对初值、非法状态、循环范围和最终答案位置。
- 能构造最小反例并手算少量状态,快速确认错误首次出现的位置。
先固定状态含义
排查时第一件事不是盯着代码,而是把状态写成完整句子。例如零钱兑换中,若定义 dp[x] 为“凑出金额恰好为 x 所需的最少硬币数”,那么 dp[0]=0 表示不选硬币即可凑出 0;无法凑出的金额则必须保持为“不可达”。
“恰好为 x”和“不超过 x”是两种不同状态。若定义写的是前者,转移却允许从任意更小金额直接继承,就已经在语义层面出错。发现某个转移无法用状态定义解释时,应先修定义或转移,而不是补特殊判断。
按固定顺序核对边界
状态含义确认后,再按下面的顺序检查。这个顺序的价值在于:前面的错误会污染后面的所有状态,越早发现越省时间。
- 检查最小合法状态是否初始化正确,例如空前缀、容量 0、长度 0。
- 检查非法或不可达状态是否与合法答案区分,例如最小值问题通常不能把不可达初始化为 0。
- 检查循环是否覆盖了定义域的首尾位置,尤其注意
<与<=、从 0 还是从 1 开始。 - 检查转移访问的下标是否可能越界,或是否把本不该参与的非法状态带入。
- 检查最终答案到底位于
dp[n]、dp[n-1]、某一整行,还是所有状态中的最优值。
最小值问题中常用一个足够大的哨兵值表示不可达。只要这个值不会与合法答案混淆,就能阻止“不可达状态 + 1”被错误当成有效解。
用最小反例手算状态表
下面用硬币 2 和 3 凑金额演示。状态定义为:dp[x] 是凑出金额恰好为 x 的最少硬币数,不可达记为 ∞。只观察金额 0 到 7,就能同时覆盖初值、不可达状态和答案位置。
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
dp[x] |
0 | ∞ | 1 | 1 | 2 | 2 | 2 | 3 |
如果程序在 x=1 就得到 0,说明非法状态初始化错了;如果 2、3 正确而 4 开始错误,更应该检查转移或循环范围;如果整张表正确但返回值错误,就直接检查答案位置。
这个思路比拿大样例反复打印更有效,因为最小反例能把干扰项降到最低。对二维 DP 也一样:只保留能触发错误的最短字符串、最小容量或最短区间,然后手算一小块表格。
用可执行程序验证边界
下面的程序直接打印几个边界金额以及对应状态表。amount + 1 一定大于任何合法的最少硬币数,因此可作为当前样例中的不可达哨兵。
def min_coins(coins, amount):
inf = amount + 1
dp = [inf] * (amount + 1)
dp[0] = 0 # 空金额是唯一确定的基础状态
for x in range(1, amount + 1):
for coin in coins:
if coin <= x and dp[x - coin] != inf:
dp[x] = min(dp[x], dp[x - coin] + 1)
shown = ["∞" if value == inf else str(value) for value in dp]
result = -1 if dp[amount] == inf else dp[amount]
return result, shown
coins = [2, 3]
for amount in [0, 1, 3, 6, 7]:
result, table = min_coins(coins, amount)
print(f"amount={amount}, result={result}, dp={table}")预期输出:
amount=0, result=0, dp=['0']
amount=1, result=-1, dp=['0', '∞']
amount=3, result=1, dp=['0', '∞', '1', '1']
amount=6, result=2, dp=['0', '∞', '1', '1', '2', '2', '2']
amount=7, result=3, dp=['0', '∞', '1', '1', '2', '2', '2', '3']实际调试时,先让程序输出第一个出错状态,再回到它依赖的前驱状态。若前驱已经错,继续向前追;若前驱正确而当前错,问题通常就在当前转移、循环边界或非法状态判断。这样可以把“整个 DP 都不对”缩小成“第一处错误是怎样产生的”。