动态规划的字符串操作

Question

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

我们必须重写字符串，使其具有一系列 "streaks"，其中相同的字母至少连续包含 K (1 ≤ K ≤ N) 次。

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

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

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。递归可以转换为 table，尽管 Ks 更高，但由于状态可能性减少，记忆可能更有效。

假设我们已经记录了 26 个前缀数组，用于使用最佳转换时间表将整个列表转换为每个字符，使用路径查找方法。这让我们可以使用函数 cost.

计算 O(1) 时间内字符串范围转换的成本

结果中的字母可以是以下三种情况之一：它是字符 c 的第 k 个实例，或者在第 k 个之前，或者在第 k 个之后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 的调用是 tabled.

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.

动态规划的字符串操作

String manipulation with dynamic programming

language-agnostic

string

algorithm

graph

dynamic