数据结构与算法 / 系统课时

定位状态定义与边界类错误

定位状态定义与边界类错误

动态规划出现错误答案时,最容易被忽略的往往不是转移式,而是状态含义和边界条件。这里用一套固定排查顺序,把定义、初值、非法状态、循环范围和答案位置逐层拆开,并用最小反例快速定位第一处错误。

学习目标

  • 能把 dp 中每个下标重新翻译成一句精确的人话,并据此检查转移是否匹配。
  • 能系统核对初值、非法状态、循环范围和最终答案位置。
  • 能构造最小反例并手算少量状态,快速确认错误首次出现的位置。

先固定状态含义

排查时第一件事不是盯着代码,而是把状态写成完整句子。例如零钱兑换中,若定义 dp[x] 为“凑出金额恰好为 x 所需的最少硬币数”,那么 dp[0]=0 表示不选硬币即可凑出 0;无法凑出的金额则必须保持为“不可达”。

“恰好为 x”和“不超过 x”是两种不同状态。若定义写的是前者,转移却允许从任意更小金额直接继承,就已经在语义层面出错。发现某个转移无法用状态定义解释时,应先修定义或转移,而不是补特殊判断。

按固定顺序核对边界

状态含义确认后,再按下面的顺序检查。这个顺序的价值在于:前面的错误会污染后面的所有状态,越早发现越省时间。

  1. 检查最小合法状态是否初始化正确,例如空前缀、容量 0、长度 0。
  2. 检查非法或不可达状态是否与合法答案区分,例如最小值问题通常不能把不可达初始化为 0。
  3. 检查循环是否覆盖了定义域的首尾位置,尤其注意 < 与 <=、从 0 还是从 1 开始。
  4. 检查转移访问的下标是否可能越界,或是否把本不该参与的非法状态带入。
  5. 检查最终答案到底位于 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 一定大于任何合法的最少硬币数,因此可作为当前样例中的不可达哨兵。

python
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}")

预期输出:

text
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 都不对”缩小成“第一处错误是怎样产生的”。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

定位状态定义与边界类错误

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通