使用动态编程进行字符串操作

Question

我有一个长度为 N 的字符串的问题，其中 (1 ≤ N ≤ 10^5)。该字符串将只有小写字母。

我们必须重写字符串，使其具有一系列“条纹”，其中同一字母至少连续出现 K (1 ≤ K ≤ N) 次。

将字符串中的单个特定字母从 i 更改为 j 需要花费 a_ij。您可以将每个字母更改为 M 种不同的可能字母。

示例:“abcde”是输入字符串。 N = 5(“abcde”的长度)，M = 5(字母为 A、B、C、D、E)，K = 2(每个字母必须至少重复 2 次)然后我们得到一个 M× M 值矩阵 a_ij，其中 a_ij 是 0…1000 范围内的整数，对于所有 i，a_ii = 0。

0 1 4 4 4

2 0 4 4 4

6 5 0 3 2

5 5 5 0 4

3 7 0 5 0

这里，从A变成A的成本是0，从A变成B的成本是1，从A变成C的成本是4，以此类推。从 B 变为 A 花费 2。

本例中的最优解是将 a 变为 b，将 d 变为 e，然后将两个 e 都变为 c。这将需要 1 + 4 + 0 + 0 = 5 次移动，最后的组合字符串将是“bbccc”。

它变得复杂，因为从使用按钮 i 切换到中间按钮 k，然后从按钮 k 切换到按钮 j，而不是直接从 i 切换到 j(或者更一般地说，可能会有从 i 开始的更改路径)并以 j 结尾，这给出了从按钮 i 最终切换到按钮 j 的最佳总体成本)。

为了解决这个问题，我把矩阵当成一个图，然后执行 Floyd Warshall 来寻找最快的时间切换字母。这将需要 O(M^3)，也就是 26^3。

我的下一步是对每个额外的字母执行动态编程以找到答案。如果有人可以就如何做到这一点给我建议，我将不胜感激!

Answer 1

这里有一些未经检验的想法。我不确定这是否足够有效(或完全解决)，但它看起来像 26 * 3 * 10^5。循环可以转换为表格，尽管具有更高的 K s，由于状态可能性减少，内存可能更有效。

假设我们已经记录了 26 个前缀数组，用于使用最佳转换时间表将整个列表转换为每个字符，使用路径查找方法。这让我们可以计算 O(1) 中字符串范围的转换成本。时间，使用函数，cost .

结果中的字母可以是以下三种情况之一:要么是 k第一个字符实例 c ，或者在 k 之前th，或者在 k 之后日。这导致一般的复发:

f(i, is_kth, c) ->
  cost(i - k + 1, i, c) + A
  where
    A = min(
      f(i - k, is_kth, c'),
      f(i - k, is_after_kth, c')
    ) forall c'

A假设较早调用 f，因为字母表是恒定的，所以需要恒定的时间已被提交。

f(i, is_before_kth, c) ->
  cost(i, i, c) + A
  where
    A = min(
      f(i - 1, is_before_kth, c),
      f(i - 1, is_kth, c'),
      f(i - 1, is_after_kth, c')
    ) forall c'

再次 A是常数时间，因为字母表是常数。

f(i, is_after_kth, c) ->
  cost(i, i, c) + A
  where
    A = min(
      f(i - 1, is_after_kth, c),
      f(i - 1, is_kth, c)
    )

A后者是常数时间。我们将寻求应用于字符串末尾每个字符的递归的最佳结果，其中任一状态 is_kth或状态 is_after_kth .