string - 在字符串中交换字符的最低成本，因此没有 3 个相同的字符是连续的

Question

我有一个只包含两个字符值的字符串:'a'或 'b' .一个字符可以换入另一个字符值。字符串中的每个字符都有一个与交换它相关的成本。我需要找到交换的最低成本，以便在结果字符串中没有 3 个具有相同值的连续字符。
如果我们有一个长度为 3 的连续字符块，那么我们只需交换最小成本字符。如果我们有一个大于 3 的块，那么我们有多种交换的可能性。我不知道如何处理这个案子。如何有效地决定在大于长度 3 的块中交换哪些字符？

Answer 1

我们可以在 O(6n) = O(n) 中解决这个问题时间和O(1)空间与 dynamic programming .
让 dp[i][state]代表最高至并包括 i 的最佳成本第 th 个字符，当最后三个字符是六个有效字符之一时 state s(即 aab、aba、baa、bba、bab、abb)。然后为 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)