我最近发现了一个竞赛问题，要求您计算在字符串中（任何位置）必须插入的最小字符数才能将其变成回文。
例如，给定字符串：“ abcbd”，我们可以通过仅插入两个字符将其转变为回文：一个在“ a”之后，另一个在“ d”之后：“ a d bcbd a ”。
这似乎是要求相同事物的类似问题的概括，只是字符只能在末尾添加-这在O（N）中使用哈希表非常简单。
我一直在尝试修改Levenshtein距离算法来解决此问题，但没有成功。任何有关如何解决此问题的帮助（不一定是有效的，我只是对任何DP解决方案都感兴趣）。
注意：这只是出于好奇。Dav提出了一种算法，可以将该算法修改为DP算法，以便轻松地在O（n ^ 2）时间和O（n ^ 2）空间中运行（并且也许O（n）具有更好的簿记）。
当然，如果您决定更改允许的操作，那么这种“幼稚”算法实际上可能会派上用场。
这是一个“天真”的算法，通过聪明的簿记可以使其更快。
给定一个字符串，我们猜测所得回文的中间位置，然后尝试计算使该字符串成为该中间周围的回文位置所需的插入数。
如果字符串的长度为n，则可能有2n + 1个中间（每个字符，在两个字符之间，紧接在字符串之前和之后）。
假设我们考虑一个中位数，它给我们两个字符串L和R（一个到左，一个到右）。
如果我们使用插入，我相信现在可以使用最长公共子序列算法（这是一种DP算法）来创建一个同时包含L和R的反向字符的“超级”字符串，请参见最短公共超序列。
选择中间，它会为您提供最小的插入数。
我相信这是O（n ^ 3）。（注意：我没有尝试证明它是真的）。
