在字符串中交换字符的最低成本，因此没有3个相同的字符是连续的
在字符串中交换字符的最低成本，因此没有3个相同的字符是连续的
提问于 2020-06-22 22:58:58
我有一个只包含两个字符值的字符串：'a'或'b'。一个字符可以换成另一个字符值。字符串中的每个字符都有一个与交换它相关的开销。我需要找到交换的最小成本，这样在结果字符串中没有3个连续的字符具有相同的值。
如果我们有一个长度为3的连续字符块，那么我们只交换最小成本的字符。如果我们有一个长度大于3的块，那么我们有许多交换的可能性。我不知道该怎么处理这个案子。如何有效地决定在长度大于3的块中交换哪些字符？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-06-23 00:17:54
我们可以用dynamic programming在O(6n) = O(n)时间和O(1)空间中解决这个问题。
当最后三个字符是六个有效的state之一(即，aab、aba、baa、bba、bab、abb)时，让dp[i][state]表示直到并包括第i个字符的最佳成本。然后是i > 2
dp[i][aab] ->
if s[i] == "a":
cost[i] + dp[i-1][baa]
else:
dp[i-1][baa]
dp[i][aba] ->
if s[i] == "a":
min(dp[i-1][aab], dp[i-1][bab])
else:
cost[i]+ min(dp[i-1][aab], dp[i-1][bab])
... (left as an exercise)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62517368
复制相关文章
相似问题
腾讯云开发者
