提问人：cracra 提问时间：12/15/2019 更新时间：12/15/2019 访问量：272
使用动态编程进行字符串操作
String manipulation with dynamic programming
问：
我有一个问题，我有一个长度为 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 和 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 结尾的更改路径，最终从按钮 i 切换到按钮 j 的总成本最高）。
为了解决这个问题，我将矩阵视为图形，然后执行 Floyd Warshall 以找到切换字母的最快时间。这将需要 O（M^3），它只有 26^3。
我的下一步是对每个额外的字母执行动态编程以找到答案。如果有人能给我建议如何做到这一点，我将不胜感激！
答：
2赞
גלעד ברקן
12/15/2019
#1
以下是一些未经测试的想法。我不确定这是否足够有效（或完全解决），但它看起来像 26 * 3 * 10^5。重复可以转换为表格，尽管 s 越高，记忆可能更有效，因为状态可能性降低。K
假设我们记录了 26 个前缀数组，用于使用最佳转换计划，使用路径查找方法将整个列表转换为每个字符。这让我们可以使用函数 .O(1)cost
结果中的字母可以是以下三种情况之一：要么是字符的第 ，要么是在 th 之前，要么是在 th 之后。这会导致一般复发：kckk
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在后者中是恒定时间。我们将寻求应用于字符串末尾的每个字符的递归的最佳结果，其中包含 state 或 state 。is_kthis_after_kth
评论
0赞
cracra
12/15/2019
你能解释一下c'是什么意思吗？
1赞
גלעד ברקן
12/15/2019
@cracra肯定：任何不是.c
0赞
cracra
12/15/2019
如果我们检查所有 c'，A 如何常数？
1赞
גלעד ברקן
12/15/2019
@cracra A 是恒定时间，因为字母表是有限的（我假设是 26？），所以每个评估都限制为 ，假设我们已经提出了对 的调用。O(|alphabet|) = O(1)f
0赞
cracra
12/15/2019
另外，我将如何使用 f 函数？我会在字符串中的每个字母上运行它，以及以什么状态运行它吗？
评论