algorithm - 通过动态规划构建最小尺寸的特里树( war 故事 : What’s Past is Prolog from The Algorithm Design Manual by Steven S Skiena)

Question

我正在阅读 Steven S Skiena 的算法设计手册，并试图了解 War Story: What’s Past is Prolog 问题的解决方案。 .问题描述的也很好here .

基本上，问题是，给定一个有序的字符串列表，给出一个最优解来构造一个最小大小的 trie(以字符串字符为节点)，条件是必须保留字符串的顺序，而字符索引可以重新排序。

也许这对于 stackoverflow 来说不是一个合适的问题，但我仍然想知道是否有人可以给我一些解决方案的提示，尤其是这种重复的论点意味着什么: the recurrence for the Dynamic Programming algorithm

Answer 1

你可以这样想:

1. 假设我们固定了第一个字符的索引。根据该位置字符的值，所有字符串都被分成 r bins(bins 本质上是子树)。

2. 我们可以独立处理每个容器。它不会更改不同 bin 中的顺序，因为不同 bin 中的两个字符串的第一个字符不同。

3. 因此，我们可以独立解决每个 bin 的问题。之后，我们只需要一条边将根连接到每个 bin(即子树)。这就是公式
   C[i_k, j_k] + 1 来自。

4. 因为我们想要最小化边的总数并且我们可以自由选择第一个位置，所以我们只是在 m 个位置中尝试所有可能的选项。

注意:假设我们可以独立地对每个子树中的其余字符重新排序，则该算法是正确的。如果不是这样，则动态规划解决方案不正确。