这道算法题的公式是什么？

来源：百度知道 编辑：UC知道 时间：2024/06/07 01:05:34
把由n个连续的A和n个连续的B(200≥n≥4)组成的字符串通过字符移动操作变成AB相间的字符串。移动规则为：每次移动以两个相邻字符为单位，这两个相邻字符之间的顺序以及其它字符之间的顺序不得改变。举例如下：

AAAABBBB →AAA##BBBAB→AAABB##BAB→A##BBAABAB→ABAB##ABAB→ABABABAB

其中，“#”代表空出的位置。

求最少的移动步数。

最少的移动步骤不清楚，但以下方法可以达到目的——
反过来思考，将AB相间的字符串，每次移动2个相邻字符，最后弄成n个连续的A和n个连续的B的字符串，那就很容易了。例如ABABABAB，只要每次将最后的“AB”，插入第二个“B”的前面就行：
ABABABAB→AABBABAB→AAABBBAB→AAAABBBB
总共要移动n-1对AB，所以可以n-1步达到目的