交换字符串中字符的最低成本，因此没有 3 个相同的字符是连续的
Minimum cost of swapping chars in string so no 3 same are consecutive
我有一个仅包含两个字符值的字符串：'a' 或 'b'。一个 char 可以换成另一个 char 值。字符串中的每个字符都有一个与交换它相关的成本。我需要找到交换的最低成本，以便在结果字符串中没有 3 个具有相同值的连续字符。
如果我们有一个长度为 3 的连续字符块，那么我们只需交换成本最低的字符。如果我们有一个长度大于 3 的块，那么我们有多种交换的可能性。我不知道如何处理这种情况。如何有效地决定在大于 3 的块中交换哪些字符？
我们可以在 O(6n) = O(n) 时间和 O(1) space 内用 dynamic programming 解决这个问题。
当最后三个字符是六个有效 state 之一（即 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)
我有一个仅包含两个字符值的字符串：'a' 或 'b'。一个 char 可以换成另一个 char 值。字符串中的每个字符都有一个与交换它相关的成本。我需要找到交换的最低成本，以便在结果字符串中没有 3 个具有相同值的连续字符。
如果我们有一个长度为 3 的连续字符块，那么我们只需交换成本最低的字符。如果我们有一个长度大于 3 的块，那么我们有多种交换的可能性。我不知道如何处理这种情况。如何有效地决定在大于 3 的块中交换哪些字符？
我们可以在 O(6n) = O(n) 时间和 O(1) space 内用 dynamic programming 解决这个问题。
当最后三个字符是六个有效 state 之一（即 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)