【问题求解II-HW3.C】单词接龙
题意概述
- 给定 $n$ 个英文单词，两个单词可以接在一起当且仅当前一个单词的最后一个字母和后一个单词的第一个字母相同。问最少删除多少个单词可以让剩下的单词全部接龙。
- $n\leq 10^5$。
从本次作业开始我们会逐渐向大家介绍简单的动态规划 (dynamic programming) 设计。动态规划是一项“很难教”的技术，因为它没有什么特别的理论基础，好的状态设计和转移优化也没有固定的模式，需要大家多看、多想、多总结。我们通过“单词接龙”这道题来向大家展示好的状态设计是如何显著减少算法时间复杂度的。
首先，删除尽量少的单词等价于选择尽量多的可接龙单词，因此我们将问题转化为寻找原单词序列的最长可接龙子序列。我们首先考虑如下最容易想到的状态：令 $dp(i)$ 表示以第 $i$ 个单词结尾的最长可接龙子序列的长度。为了计算这个状态，我们需要在 i-th 前找到另外一个单词，满足可以和 i-th 接上。因此转移方程可以写为 $$ dp(i) = 1 + \max_{k\in [1, i-1], word_k \to word_i} dp(k) $$ 其中 $word_i\to word_j$ 表示第 $i$ 个词的最后一个字母和第 $j$ 个词的第一个字母相同。式子最前方的 1 表示第 $i$ 个单词贡献的序列长度。计算完所有的 dp 值之后，$\max_{k=1}^n dp(k)$ 即为答案。
这自然是一个正确的算法，但计算 $dp(i)$ 时需要依次枚举前面的所有单词，从而时间复杂度达到了 $O(n^2)$，在本题的数据规模下不可接受。
优化状态设计的动机是：我们最关心的其实是单词的开头/结尾字母，而小写字母一共只有 26 个。因此我们应该在这方面作文章，把每次遍历前面所有单词的过程节省掉。考虑如下状态：令 $dp(i, ch)$ 表示在前 $i$ 个单词中，以字符 $ch$ 结尾的最长可接龙子序列的长度 (注意！不再要求一定以 $word_i$ 结尾！)。转移考虑对以下两种情况取 max：
- 最长子序列不包括第 $i$ 个单词: $dp(i-1, ch)$。
- 最长子序列包括第 $i$ 个单词，且第 $i$ 个单词确实以 $ch$ 结尾: 设第 $i$ 个单词的开头字符为 $ch’$，则这种情况的最长序列长度为 $dp(i-1, ch’) + 1$。
因此状态转移方程可以写为
$$ dp(i, ch) = \begin{cases} \max\{dp(i-1, ch), dp(i-1, \text{start}(word_i)) + 1\} &, \text{end}(word_i) = ch\\ dp(i-1, ch)&, \text{otherwise} \end{cases} $$
可以看到，虽然状态的数量上升到了 $O(n|\Sigma|)$，但转移的代价变成了 $O(1)$，所以总时间复杂度降低到了 $O(|\Sigma|n)$，其中 $\Sigma$ 为字符集，在本题中 $|\Sigma|=26$，可以通过。
有没有什么小技巧可以略微优化一下复杂度？
上述状态转移方程中，我们每次只会对一个 $ch$ 更新 dp，其余的都是照抄。而且 $dp(i, ch)$ 的计算只会用到 $dp(i-1, ch)$ 的结果，因此我们可以把状态的第一维省掉，把代码写成如下形式：
dp = [0] * MAX_CHARACTER # 长度为 |Sigma| 的数组
for i in range(1, n + 1):
# 此时的 dp[ch] 存储的是方程式中 dp(i-1, ch) 的值
startch, endch = strings[i].start, strings[i].end
dp[endch] = max(dp[endch], dp[startch] + 1)
# 根据转移方程，此时 dp[endch] 的值是 dp(i, ch) 的值
# 又因为其他的 dp[ch] 不需要改变，所以自动“升级”成了 dp(i, ch)
# 至此，dp[ch] 存储了方程式中 dp(i, ch) 的值
可以看到，省掉了第一维之后，动态规划的时间复杂度下降到了 $O(n)$，空间复杂度下降到了 $O(|\Sigma|)$ (不考虑存储字符串的额外代价)。如果字符集的大小达到了很大的级别 (比如 unicode 中的所有字符)，那么这一简单的优化可以节省大量的时间和存储。
第一个 dp 思路真的是“死胡同”吗？
再来重温一下状态转移方程
$$ dp(i) = 1 + \max_{k\in [1, i), word_k \to word_i} dp(k) $$
在考虑 $dp(i)$ 的转移时，我们在意的是所有的那些结尾字母与 $word_i$ 开头字母相同的位置的 dp 的最大值。每次把 1 到 i-1 扫一遍效率太低，但注意我们在做到 $dp(i)$ 时，之前的所有 dp 值已经求好了，因此我们可以额外对每种结尾字母维护当前最大值，从而实现 $O(1)$ 转移。
形式化地，令 $$ maxdp(i, ch)\triangleq \max_{k\in [1, i],\text{end}(word_k)=ch} dp(k) $$ 则我们可以同时写出 dp 和 maxdp 的状态转移方程
$$ \begin{align} dp(i) &= 1 + maxdp(i-1, \text{start}(word_i))\\ maxdp(i, ch) &= \begin{cases} \max\{maxdp(i-1, ch), dp(i)\} &, \text{end}(word_i) = ch\\ maxdp(i-1, ch) &, \text{otherwise} \end{cases} \end{align} $$
两个转移都是 $O(1)$ 的，而且由于 $dp(i)$ 只用到 $maxdp(i-1, ch)$，所以我们可以用和类似的技巧将 maxdp 的第一维度省去，将代码写成类似下面的模样：
for i in range(1, n + 1):
startch, endch = strings[i].start, strings[i].end
dp[i] = 1 + maxdp[startch]
maxdp[endch] = max(maxdp[endch], dp[i])
你又可以发现一件事情：$dp(i)$ 在当前循环算完立即使用，且后续再也不会使用，所以可以把 $dp(i)$ 省略：
for i in range(1, n + 1):
startch, endch = strings[i].start, strings[i].end
maxdp[s.endch] = max(maxdp[endch], 1 + maxdp[startch])
和之前的代码对比一下，你会发现除了数组名字不一样，其他完全一样。我们用两条看上去不太相同的思考路径得到了相同的结果，但实际上它们的本质是一致的：
动态规划状态设计就像给当前时刻做一张“快照”。你需要想清楚快照中保存怎样的性质可以完整地刻画当前的状态并为后续所用。在此基础上，记录的性质应当越少越好。 在这个问题中，每个接龙字符串序列的最后一个字符是最本质地刻画特征的性质，而最后一个字符串的下标并不是 ($i+1$ 往后的状态并不关心 $[1,i]$ 中结尾为 $ch$ 的最长接龙字符串序列的最后一个字符串是 $[1, i]$ 中的哪一个)。这就是第一个 dp 方向错误的根本原因。
大家日后要做的，就是稳准狠地抓住一个状态最本质的性质。