我想在spoj上解决这个问题：http://www.spoj.pl/problems/EDIT/
我试图得到一个体面的递归算法的描述，但我失败了，因为我的思想一直在旋转圈你们能帮我解决这个问题吗？我将试着描述我试图解决这个问题的方法。
基本上我想解决一个j-I大小的问题，其中I是起始索引，j是结束索引现在，应该有两个案子了。如果j-i是偶数，那么开始字母和结束字母必须是同一个大小写，当j-i是奇数时，它们必须是相反的大小写。我还想减少较小规模的问题（j-I-1或j-I-2），但我觉得如果我知道一个较小问题的解决方案，那么构造一个较大问题的解决方案时也应该考虑到较小问题的起始和结束字母情况这正是我困惑的地方。你们能把我的想法放在正确的轨道上吗？
最佳答案
我认为递归不是解决这个问题的最好方法如果我们采取不同的方法，它可以很快解决！
让我们考虑二进制字符串。假设大写字符是1，小写字符是0例如
AaAaB -> 10101
ABaa -> 1100
a -> 0
“正确”的交替链是10101010。或010101010。。
我们调用将一个字符串更改为另一个字符串所需的最小替换数Hamming distance。我们要找到的是输入二进制字符串和两个相同长度的交替链之一之间的最小hamming距离。
这并不困难：我们将每个字符串进行异或运算，然后计算1s的数目。（link）例如，让我们考虑以下字符串：abaa。
我们将其转换为二进制：
阿巴->1100
我们只生成两条长度为4的交替链：
1010个
0101号
我们将它们与输入进行异或：
1100异或1010=0101
1100异或0101=1010
我们计算结果中的1，取最小值。在这种情况下，是2。
我用Java编写了这个过程，并进行了一些小的优化（缓冲I/O，不需要生成交替链），它被接受了：（0.60秒1）。