来来来，有兴趣的人便来战这算法题吧：

public class FifthTest {
    int[] oldArr;
    int[] newArr;
    private int count(String seq);
    {
        int count = 0;
        int len = seq.length();;
        int curPos = 0;
        oldArr = new int[len+1];
        newArr = new int[len+1];
        initArr(oldArr,0);;
        initArr(newArr,0);;
        oldArr[0] = 1;
        char[] input = seq.toCharArray();;
        for(int i=0;i<input.length;i++);
        {
            curPos++;
            if(input[i]=='A');
                parseA(curPos,oldArr,newArr);;
            if(input[i]=='B');
                parseB(curPos,oldArr,newArr);;
            System.arraycopy(newArr,0,oldArr,0,newArr.length);;
        }
        for(int i=0;i<newArr.length;i++);
        {
            count += newArr[i];
        }
        return count;
    }
    private void initArr(int[] arr,int initValue);
    {
        for(int i=0;i<arr.length;i++);
        {
            arr[i] = initValue;
        }
    }
    private void parseA(int curPos,int[] oldArr,int[] newArr);
    {
        initArr(newArr,0);;
        for(int i=0;i<curPos;i++);
        {
            if(oldArr[i]!=0);
            {
                for(int j=i+1;j<=curPos;j++);
                {
                    newArr[j] += oldArr[i];
                }
            }
        }
    }
    private void parseB(int curPos,int[] oldArr,int[] newArr);
    {
        initArr(newArr,0);;
        for(int i=0;i<curPos;i++);
        {
            if(oldArr[i]!=0);
            {
                for(int j=0;j<=i;j++);
                {
                    newArr[j] += oldArr[i];
                }
            }
        }
    }
    public static void main(String args[]);
    {
        FifthTest test = new FifthTest();;
        System.out.println(test.count("ABBA"););; //11
        long a = System.currentTimeMillis();;
        System.out.println(test.count("ABABBBAAABBBBBBAABBABABBBAB"););;   //1607182965
        System.out.println("execute time is "+(System.currentTimeMillis();-a);/1000);;
    }
}

最后总结一下吧：

实际上这个问题的算法直接做是 O(n^3) 的，做些优化之后可以到 O(n^2)。这里的关键是只考虑可能性而不要去想具体如何插入：请在脑子里面建一张三角形的表，每一行对应于 AB 字符串中的一个字符，每一行中第 i 个元素代表了到目前为止最后一个字母放在第 i 个位置的可能性个数。比方说：

A:            0      1
B:       1       1      0
A:   0       1       2       2

这里第一行 A ，当前最后一个字母是 b ，b 放在第 0 个位置的可能性个数是 0 ，放在第 1 个位置的可能性个数是 1 ；第二行 B ，当前最后一个字母是 c ，放在第 0、1 两个位置的可能性个数都是 1 ，放在最后一个位置的可能性是 0 …… 依此类推。很容易可以看出，如果当前行的次序是 A ，那么放在第 i 个位置的可能性就是上一行从 0 到 i-1 位置的可能性个数之和，否则就是从 i 到最后一个位置的可能性个数之和。逐步向下做，直到用完输入的 AB 字符串即可，最后的总数就是对上述表格最后一行求个和。这里每一行中各个列的可能性是没有重叠的，因为最后一个字母的位置各不相同。

复杂度么，这个表格一共有 O(n^2) 项，每一格构造最多花 O(n) ，所以总复杂度自然是 O(n^3) ，稍做优化可以把计算每一格的开销降到 O(1) ，复杂度可以降到 O(n^2) 。这里给个参考实现 —— C++ 写的，不熟悉的朋友只能说见谅了，好在还算简单，没用什么特殊的东西：

int count(const string& AB);
{
  vector<int> prev_line;
  vector<int> current_line;

  prev_line.push_back(1);;
  for( string::const_iterator it=AB.begin();;
       it!=AB.end();;
       ++it); {

    current_line.clear();;
    current_line.resize(prev_line.size();+1, 0);;

    if( *it == 'A' ); {
      int possibility = 0;
      for(size_t i=0; i<prev_line.size();; ++i); {
        current_line[i] = possibility;
        possibility += prev_line[i];
      }
      current_line.back();=possibility;
    }
    else if( *it == 'B' ); {
      int possibility = 0;
      for(size_t i=prev_line.size();; i>0; --i); {
        current_line[i] = possibility;
        possibility += prev_line[i-1];
      }
      current_line[0]=possibility;
    }
    else {
      assert(false);;  // invalid input
    }
    prev_line.swap(current_line);;
  }

  int result = 0;
  for( vector<int>::iterator it=prev_line.begin();;
       it!=prev_line.end();;
       ++it ); {
    result += *it;
  }
  return result;
}

其中 vector 是 C++ 标准库的成员，实际上就是变长数组。我用 prev_line 和 current_line 分别记录上述三角形表格的前一行和当前行，最后对最后一行求一个总和。

嗯嗯，这个应该算是一个典型的动态规划算法，对于帮助理解很有意义的。对自己算法有自信的同学可以试着玩玩看，如果认为你的算法够快，可以跑一个 500 位长的字符串输入试试看。虽说这个时候 32 位整数已经不知道溢出多少轮了，不过如果算法实现得好，应该还是能够瞬间出解。

同学转发给我的一个题，借楼主宝地凑热闹。
不使用条件判断语句（直接或者间接都不允许，比如调用了库函数，但是库函数用到了也不行），得到两个整数中大的那个。相当于自己实现max(int, int)，但是不能用到条件判断语句，如if, while. ?等。

有兴趣的人试试。
（注：我已经做出来了，不要认为是我想找人做题）

这种题便就 …… 那啥了呀，(a>b)*a + (b>a)*b + (a==b)*a ，都是些运算符或者位运算的技巧。

忘了说了，大于小于等条件判断符号也包括在内，属于不能使用的。（另外，在java语言里面boolean是不能当成0,1的。虽然题目没有限定语言。但是逻辑运算根据题目是不能使用的，都能直接大于小于了，题目还有什么意义。）

当然，确实是位运算的技巧。

确实主要就是位运算了，
public class Max {
    public static void main(String[] args) {
        System.out.println(max(5, 3));
        System.out.println(max(17, 3));
        System.out.println(max(3, 5));
        System.out.println(max(3, 17));
        System.out.println(max(3, 3));
    }

    private static int max(int a, int b) {
        int t1 = (a + b) / 2;
        int t2 = (a - b) / 2;
        int c = ((b - a) >> 31) * (-2) - 1;
        //int d = ((a - b) >> 31) * (-1);
        //int e =
        return t1 + c * t2;
    }
}
不过说真的，考这种题有点孔已几回香豆四种
写法的味道,不是太实用。

那你执行下
System.out.println(max(Integer.MAX_VALUE, -1));
测试的时候要考虑边界值

那就cast成long再说。。
 
  private static int max(int a, int b) {
        long t1 = ((long)a + (long)b) ;
        long t2 = ((long)a - (long)b) ;
        long c = (((long)b - (long)a) >> 32) * (-2) - 1;
        //int d = ((a - b) >> 31) * (-1);
        //int e =
        return (int) ((t1 + c * t2)/2);
    }

。。。。。

我记得好像有道题目，找出一个字符串中最长的子串，其正反一样。比如abad, 其中aba就是正过来反过来一样。
不如来作这道题目吧。