你给出一个二进制串（只有0和1级的）š长度的Ñ。
您想通过执行以下操作最少次数将s转换为空字符串。
您的任务是确定将s转换为空字符串所需的最少操作数。
注意：
字符串s的交替子序列定义如下
限制条件：
1 <= T <= 10
1 <= n <= 10^6
输入样例：
1
10
0100100111
样本输出：
3
说明：
从“ 01 0 01 0 01 11”中删除子序列“ 010101” ，使其成为“ 0011”
从“ 0 01 1 ”中删除子序列“ 01” ，使其成为“ 01”
最后，从“ 01 ”中删除子序列“ 01” ，使其成为“”（空二进制字符串）
希望能对您有所帮助，谢谢。
想象一下，对于某个字符串x，您知道可以使用以'0'结尾的m个操作和以'1'结尾的n个操作来擦除它，总共（m + n）个操作。我们将写这个（m，n）。这并不一定是最好的结果，但它是一个结果。
现在，您对字符串x0知道什么？
如果n> 1，则可以在这些1尾运算中添加一个零，将其变为零尾运算，因此可以在（m + 1，n-1）个运算中清除x0。
当然，您总是可以添加一个新的0结束操作，以便可以在（m + 1，n）个操作中清除x0。
同样，您可以在（m，n + 1）个操作中清除x1，如果m> 0则可以清除（m-1，n + 1）。
显然，只有一种方法可以清除空字符串，并且使用（0,0）操作，因此从头到尾进行工作，您可以计算出所有各种（m，n）可能性来清除每个前缀，直到获得到最后，总和最小的就是您的答案。那将是一个O（n 2）算法。
但是，在任何情况下，选择（m + 1，n）而不是（m + 1，n-1）都不会使您总体上使用更少的运算。同样，在任何情况下都不会选择（m，n + 1）胜过（m-1，n + 1）。
因此，我们不必担心每个位置的两个可能选择，而是可以确定确定单个最佳选择，具体取决于下一个字符是0还是1：
以x =“”和（m，n）=（0,0）开头：
当下一个字符为0时，则x <-x +“ 0”和（m，n）<-（m + 1，max（n-1,0））
当下一个字符为1时，则x <-x +“ 1”和（m，n）<-（max（m-1,0），n + 1）
当您到达字符串的末尾时，m + n是可以清除它的最少数量的操作。
或者，使用伪代码：
m = 0; n = 0;
for (char in string) {
if (char == 0') {
m = m+1;
n = max(n-1,0);
} else {
m = max(m-1,0);
n = n+1;
}
}
return m+n;
十分简单。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句