算法补课 · 下标是金额，值是枚数：动态规划的状态、递推与回溯

Unigram 的确定性编码用动态规划保存每个前缀的最高分。 最后一个词条可以从位置 4 直接跨到位置 6，位置 5 的答案虽然已经算过，却没有被最终路径采用。

这里有三个问题值得单独展开：表里的一个格子到底代表什么，为什么能直接复用它，以及存下分数之后怎样找回路径？ 先把概率和字符串放到一边，用一个只有七个格子的例子，把这三件事算完。

先把问题定死：恰好凑齐，枚数最少

有面额为 1、3、4 元的硬币，每种可以用无限枚。目标是恰好凑出 6 元，用的硬币越少越好。

每次先拿不超过剩余金额的最大面额，会得到 4 + 1 + 1。这个贪心规则在这组面额下失败了。 原因是：眼前面额最大，不保证剩下的钱最好凑。

下面换一种做法：先求出凑 0、1、2、… 元各自最少需要几枚，再组合出 6 元的答案。 “动态规划”在这里的具体动作，就是把会重复用到的小问题答案保存下来，按依赖顺序计算更大的问题。

问题的三个条件都要保留：面额是正整数、数量不限、必须恰好凑齐。它们会分别决定计算顺序、状态是否够用，以及哪些候选合法。

下标是金额，值是枚数

定义：

dp[x] = 恰好凑出 x 元，最少需要的硬币枚数

例如 dp[5] = 2，读作：凑 5 元最少要 2 枚，一种凑法是 4 + 1。 方括号里的 5 和读出来的 2，单位不同。

先用金额定位，再读出枚数。 dp[3] 里的 3 不是三枚硬币；这个例子中 dp[3] = 1，因为一枚 3 元就够了。

起点为什么是 0，其他位置为什么是 ∞

dp = [0, float("inf"), float("inf"), float("inf"),
      float("inf"), float("inf"), float("inf")]
choice = [None] * 7

dp[0] = 0 是一个已经知道的答案：不拿任何硬币，就恰好凑出 0 元。 它也是后续计算的起点。例如最后一枚用 3 元凑 3 元，会读取 dp[0]。

正金额先填 ∞，表示尚未找到方案。这样第一个有限候选一定能把它替换掉。 如果也初始化成 0，后面每个候选都大于 0，“更少才更新”就永远不会发生。

某个金额的候选全部检查完后，若还保留 ∞，才说明它不可达。 本例有 1 元硬币，所有非负整数金额都可达；只有 2、4 元硬币时，3 元就会一直留在 ∞。

★ 递推式：先假设最后一枚是什么

要凑 x 元，假设最后一枚是 c 元。把它拿掉，前面就必须恰好凑出 x − c 元：

金额：(x − c) + c = x       元 + 元 = 元
枚数：dp[x − c] + 1         枚 + 枚 = 枚

+1 加的是一枚硬币，不是 1 元。即使最后放的是 4 元，枚数也只加 1。

对每一种合法的末枚都试一次，取最少枚数：

dp[0] = 0

dp[x] = min { dp[x − c] + 1 | c ∈ {1, 3, 4}, c ≤ x }

没有可行候选时，最小值按 ∞ 处理。c > x 的面额直接跳过；较小金额不可达时，也无法由它接出新方案。

为什么前面可以只留最优解

假设某个凑 x 元的最优方案，最后一枚为 c，前面的部分用了 m 枚。

如果前面不是凑 x − c 元的最优方案，就存在一种只用 m′ < m 枚的替代凑法。 换掉前面，再接上同一枚 c：

原方案：m  + 1 枚，金额仍为 x
新方案：m′ + 1 枚，金额仍为 x

m′ < m  ⇒  m′ + 1 < m + 1

这与原方案“最优”矛盾。因此，固定最后一枚后，前面的部分也必须最优。 这就是这个问题的最优子结构，不是额外背下来的前提，而是上面那次替换推出的性质。

再把两边合起来看：

1. 任意完整方案都有最后一枚，它必然属于合法面额之一，因此不会漏掉某种结尾。
2. 对固定的最后一枚，查到的最优前缀再加这一枚，是一个真实可行的方案。
3. 在这些候选里取最小值，得到的就是全部方案的最少枚数。

没有枚举每条完整路径，但覆盖了每一种可能的最后一步。 能省下来的，正是前面已经求过的那一段。

为什么一个金额就足够描述状态

两条路径都凑出 4 元：一条用 [4]，另一条用 [1, 3]。之后它们能继续添加的硬币完全一样，仍是无限的 1、3、4 元。 所以只要到达同一个金额，多用一枚的路径就不会在后面反超。表中留最少枚数即可。

这里用到了数量不限。若每枚硬币只能使用一次，走过哪条路径会影响剩余可用硬币，不能照搬这份递推和循环。 那类问题需要把“哪些硬币已允许使用”纳入推理；也可以压成一维数组，但必须配合不同的遍历顺序，不能把这里的写法直接拿过去。

从小到大算，为什么不会读到半成品

所有面额都大于 0，所以：

x − c < x

按 x = 1 → 2 → … → 6 计算时，每个合法候选依赖的格子都在左边，已经完成。 这给出了一个直接的归纳证明：dp[0] 正确；假设所有更小金额已经正确，上一节的递推就能正确求出当前金额。 于是从 1 算到 6，全表都正确。

一轮只求一个金额。 外层有六轮，每一轮内部按 c = 1、3、4 检查三种末枚。 轮内的 dp[x] 是“已经检查的候选里最好的一项”；全部检查完，它才成为这个金额的最终答案。

表里的候选都是枚数。面额只用来决定查哪个格子。

并列不能让这一轮提前结束

第四轮先得到 2、2，暂时并列。第三个候选却是 dp[0] + 1 = 1，还能继续变好。 因此看到相等，只能决定“这一项不用替换记录”，不能决定“本轮已经找到最终最优解”。

第五轮的 2、3、2 才是最终有两条并列最优路径：4 + 1 和 1 + 4。 本例只在严格更少时更新，保留先找到的 4 + 1，所以 choice[5] = 1。 如果面额按 4、3、1 的顺序检查，最后面额会变成 4，但最少枚数仍是 2。

choice 保存一条最优路径的线索。它不表示最优路径只有一条，也不枚举全部并列方案。

把第六轮放慢：三个候选分别查哪里

这一轮开始时，金额 0～5 的答案已经固定，只有 dp[6] = ∞ 还在等候选。

最后一枚假设是 1 元

剩余金额：6 − 1 = 5 元
查表：    dp[5] = 2 枚
候选：    2 + 1 = 3 枚       对应 4 + 1 + 1 = 6 元
比较：    3 < ∞
更新：    dp[6] = 3，choice[6] = 1

3 枚目前最好，先记住；后面还有两个末枚没有试。

最后一枚假设是 3 元

剩余金额：6 − 3 = 3 元
查表：    dp[3] = 1 枚
候选：    1 + 1 = 2 枚       对应 3 + 3 = 6 元
比较：    2 < 3
更新：    dp[6] = 2，choice[6] = 3

判断发生在写入之前：用候选 2 与旧值 3 比较，成立后才写入 2。 如果看到更新后的表，再拿 2 与 2 比，就会误以为“相等也发生了更新”。

最后一枚假设是 4 元

剩余金额：6 − 4 = 2 元
查表：    dp[2] = 2 枚
候选：    2 + 1 = 3 枚       对应 1 + 1 + 4 = 6 元
比较：    3 > 2
保留：    dp[6] = 2，choice[6] = 3

三种末枚都检查完，才固定 6 元的答案：2 枚。

为什么不把历史格子都扫一遍

固定 x = 6、c = 3 后，前面的金额已经唯一确定为 6 − 3 = 3。 所以只读 dp[3]，不是从 dp[0] 到 dp[5] 再找一遍。

如果拿 dp[2] 的方案再放一枚 3 元，凑出来的是 2 + 3 = 5 元。 它属于第五轮的候选，不满足第六轮“恰好凑 6 元”的要求。

子问题比最终目标小当然可以，前提是：子问题金额 + 本次末枚面额 = 当前这一轮的金额。

dp 告诉你几枚，choice 带你找回哪几枚

最终两张表是：

金额 x：    0     1  2  3  4  5  6
dp[x]：     0     1  2  1  1  2  2       枚
choice[x]： None  1  1  3  4  1  3       元

dp[6] = 2 只给出枚数。要恢复硬币，从目标金额开始读 choice：

注意，这次是金额减面额。填表时的 +1 算枚数，回溯时的 −c 算剩余金额，不能混用。

为什么每次沿 choice 都能走下去？记录写入时就满足：

c = choice[x]
dp[x] = dp[x − c] + 1

因此每取出一枚，剩余金额严格减小，剩余所需枚数也正好少 1。 对一个可达目标，最终会回到 dp[0] = 0，取出的硬币数量恰好等于最初的 dp[target]。

填表顺序与最终路径是两回事

填表：1 → 2 → 3 → 4 → 5 → 6     把每个子问题准备好
回溯：6 → 3 → 0                 只找回被最终方案选中的部分

算过 dp[5]，不意味着最后必须经过 5。它为“最后一枚是 1 元”提供了候选，比较失败后就没有进入最终方案。

回溯是从最后一枚往前取，得到的是路径的逆序。硬币的排列不影响总金额；如果要恢复正向排列，就把结果反转。 分词时顺序有意义，回溯得到的 Token 列表必须反转后才能输出。

让六轮填表与回溯连续走一遍

动画保留全部 50 个步骤：初始化、六轮取金额与检查末枚，再到回溯。 50 步是把读数、计算和更新分开展示，外层循环仍然只有六轮。

点击记忆表里的金额，可以跳到对应轮的开头。建议先单步看第六轮，再回看第四轮的“先并列、后改进”。 每一步下方都列出通用规则、本步代入和判断结果；比较使用写入前的旧值。

三个结束条件分别是：

把推导原样写成代码

下面的实现保留输入检查、不可达情况和回溯；只用 Python 标准语法。 调用时面额的顺序，就是并列候选的优先顺序。

def min_coins(coins, target):
    if type(target) is not int or target < 0:
        raise ValueError("target must be a non-negative integer")
    coins = tuple(coins)
    if any(type(c) is not int or c <= 0 for c in coins):
        raise ValueError("coin values must be positive integers")

    inf = float("inf")
    dp = [inf] * (target + 1)
    choice = [None] * (target + 1)
    dp[0] = 0

    for x in range(1, target + 1):
        for c in coins:
            if c > x:
                continue
            if dp[x - c] == inf:
                continue
            candidate = dp[x - c] + 1
            if candidate < dp[x]:
                dp[x] = candidate
                choice[x] = c

    if dp[target] == inf:
        return dp, choice, []

    picked = []
    remaining = target
    while remaining > 0:
        c = choice[remaining]
        picked.append(c)
        remaining -= c
    return dp, choice, picked

dp, choice, picked = min_coins([1, 3, 4], 6)
print(dp)       # [0, 1, 2, 1, 1, 2, 2]
print(choice)   # [None, 1, 1, 3, 4, 1, 3]
print(picked)   # [3, 3]

if c > x 必须发生在查表之前。Python 的负下标合法，dp[-1] 会读数组末尾；那不是这里需要的“负金额”，不会自动替你报错。

零目标和不可达目标，不能靠空列表区分

判断可不可达，要看 dp[target]，不能只看返回的硬币列表是不是空。

省掉的计算在哪里

dp[3] 在第四轮尝试 1 元末枚时会被读到，第六轮尝试 3 元末枚时又会被读到。 这两次需要的是同一个子问题，不必把“怎样凑 3 元”重新搜索两遍。这叫重叠子问题。

设目标金额为 A，面额种类为 K，双重循环最多检查 A × K 个候选，填表时间为 O(AK)。 dp 和 choice 各有 A + 1 个格子，空间为 O(A)；回溯每取出一枚走一步。 因为最小面额至少为 1，结果最多 A 枚。这个复杂度按金额数值 A 计，不是按写下 A 所需的位数计。

动画为逐步展示另外保存了快照和完整路径，不属于上面这份算法的空间账。 实际求解只存两个数组，不需要为每个金额复制一整条路径。

实算核对的范围

用按硬币枚数逐层扩展的广度优先搜索（BFS）做独立对照：每加一枚走一条边，首次到达某个金额的层数就是最少枚数。 面额取 [1,3,4]、[2,4]、[2,5]、[1]、[4,3,1]、[]，目标遍历 0～12，共 78 组输入。

每组都检查整张 dp、每个可达状态的 choice 等式，以及回溯硬币的面额和与数量。 全部一致；零目标、不可达目标、空面额表与面额换序也在范围内。有限测试用于核对代码，递推对任意合法输入成立的理由仍是前面的替换与归纳证明。

回到 Unigram：换了分数，仍然是在比较最后一步

硬币例子里，状态由金额确定。Unigram 的确定性编码里，状态由文本前缀的结束边界确定：

设词条非空、概率为正，text[j:i] 表示从边界 j 到边界 i 的那段文字。 枚举词表中恰好在 i 结束的合法词条：

best[i] = max { best[j] + log p(text[j:i])
                | 0 ≤ j < i，text[j:i] 在词表中 }

对固定的最后词条，它的 log p 是同一个数。前缀分数更低，接上它后仍然更低，因此只保留该边界的最高分就够了。 Unigram 的词条概率不依赖前一个词条，这使“前缀结束在哪里”足以作为这里的状态。

对 abcabc，边界写成：

0 a 1 b 2 c 3 a 4 b 5 c 6

若词表为 a、b、c、ab、bc、abc，在边界 6 结束的词条只有三种：

最后用 bc 时，必须读取 4；读取 5 再接 bc 就不能恰好覆盖这段文本。 如果胜出的末词条是 bc，最终路径就走 4 → 6，即使 best[5] 已经算好，也可以不用它。 这与硬币表里算过金额 5，却最终沿 6 → 3 → 0 回溯，是同一种结构。

Viterbi 求的是最高分路径。训练时的期望统计还要累计多条切分的贡献，使用的是求和或对数域的 logsumexp，不能把“一条最优路径”代替“全部路径的加权贡献”。 这两种目标在 Unigram 原始论文 §3.2 中分别对应最高概率切分与边缘似然。

下次遇到一行 dp[...]，先把它读成一句完整的话：这个下标定义了哪个小问题，格子里存的是哪种量，最后一步又把它接到了哪里。 状态的含义确定之后，查哪个格子、加什么、比什么，以及如何回溯，才都有了依据。