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

我还以为可以用算法公式求算出来， 嘿嘿，一阵组合概率胡乱堆砌了个公式往上放，结果还是错了。 
不过还是很佩服femoto，有机会再讨教一些算法上面的问题。 大学没学好，基础很差阿。   

:x 
题目都没看明白...........
倒底啥是AB啊........

根据这个三角形还能往下演算的

                  1

             1                              1
      1          2                  2          1     
  1    3    3      5        5      3    3    1
1 4 4 6 9 9 11 16 16 11 9 9 6 4 4 1

凑个热闹，虽然femto前面已经做出来了，但是我在做出来之前刻意没有看他的代码。另外做的仓促，请大家不要拿设计，重构之类的词汇往我身上砸。

class Pos {
    int before = 0;
    int after = 0;
    public Pos(int before, int after); {
        this.before = before;
        this.after = after;
    }
}

public class Counter {
    public static void main(String[] args); {
        Counter c = new Counter();;
        int num = c.count(args[0]);;
        System.out.println(num);;
    }
    
    public int count(String str); {
        char[] def = str.toCharArray();;
        Pos[] poses = null;
        if (def[0] == 'A'); {
            poses = new Pos[1];
            poses[0] = new Pos(1, 0);;
        } else {
            poses = new Pos[1];
            poses[0] = new Pos(0, 1);;
        }
        for (int i = 1; i < def.length; i++); {
            Pos[] temp = new Pos[0];
            for (int j = 0; j < poses.length; j++); {
                Pos[] newPos = calc(poses[j], def[i]);;
                Pos[] tmp = new Pos[temp.length + newPos.length];
                System.arraycopy(temp, 0, tmp, 0, temp.length);;
                System.arraycopy(newPos, 0, tmp, temp.length, newPos.length);;
                temp = tmp;
            }
            poses = temp;
        }
        return poses.length;
    }

    private Pos[] calc(Pos p, char def); {
        Pos[] poses = null;
        if (def == 'A'); {
            poses = new Pos[p.after + 1];
            for (int i = 0; i < p.after + 1; i++); {
                poses[i] = new Pos(p.before+p.after+1-i, i);;
            }
        } else {
            poses = new Pos[p.before + 1];
            for (int i = 0; i < p.before + 1; i++); {
                poses[i] = new Pos(i, p.before+p.after+1-i);;
            }
        }
        return poses;
    }
}

随便挑了femto的几个来测试了下
java Counter ABAB
16
java Counter ABBA
11


这个算法也类似于穷举法，所以一旦输入过长也就慢的无法忍受了。femto的也类似的。10位以上就出不来了。

看来用数学公式推导才是正途！

really ？两位的代码虽然没有细看，然则也是扫过一眼的，应该都是逐行构造三角形表格的做法，这区区 O(N^3) 的复杂度，至于弄到这样么？我自己用 C++写的参考实现，不要说 10 位，20 位也是瞬间出解。

那么这里存在两种可能：第一是 java 的某些东西实现太差，有些基本操作的复杂度不对头；第二是两位的算法实现有问题，复杂度不是 O(n^3) 。这个回头有功夫的时候我下个 java 编译器来试一下。



其实不然。
不是所有的递归关系都能写成传统意义上的“数学公式”的，再者对于搞计算的人来说，就算给出了数学公式，一样需要构造算法来计算对于给定的输入，输出究竟是多少。所以其实直接写算法和试图构造一个“数学公式”再来写算法，两者没有多少本质的区别。

是算法问题，复杂度不是O(n^3)
如果楼主的O(n^3) 算法是15分钟内做出来的，没别的话好说的，pf就是了。

其实关键是思路，如果思路有了，那么实现上出了问题导致复杂度上升还是可以补救的。所以说，做算法题还是应该先讲自己的思路再张贴代码，概因看别人的程序是很伤神的事情，特别是这种算法题 ……

不过这题是不难的，学过动态规划的人应该都能很容易想到这个 O(n^3) 的算法，接下来的速度只是看训练是否充分而已。只是国内很多大学计算机系居然不开算法课，这个就 …… 那啥了。

动态规划啊？没学过...
  我的算法就是记录最后一个字符所在位置,
字串长度为0的时候,相当于a , lastCharPos = 0;
字串为1的时候
如果是A,那么b可以在已有序列里头放在a之后，共有1个位置,lastCharPos(对于b)=1
如果是B,那么b可以在已有序列里头放在a之前，共有1个位置,lastCharPos(对于b)=0,
然后AA,c在b之后,因为lastCharPos(对于b)=1,所以c有一个位置可以放,lastCharPos(对于c)=2
然后AB,c在b之前,因为lastCharPos(对于b)=1,所以c有2个位置可以放,lastCharPos(对于c)=0或者
lastCharPos(对于c)=1

以此类推，只记录lastCharPos,就可以推算出下一步
可能有的位置,加总即可。
循环有3个，
一个跌待序列
一个跌待所有可能的lastCharPos,
然后一个跌待在count子函数里，记下所有可能的lastCharPos,
怀疑可能是记录lastCharPos的复杂度增大，
所以达不到O(n^3)

优化了一下算法
/**
* author     femto
* Date: 2005-8-14
*/
public class Counter {

    //private List tmpLastCharPoses = new ArrayList();
    private int[] tmpPosCounts;

    public int count(String s) {

        char[] chars = s.toCharArray();
        int result = 0;
        int[] posCounts;
        tmpPosCounts = new int[1];
        tmpPosCounts[0] = 1;

        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            posCounts = tmpPosCounts;
            result = 0;
            tmpPosCounts = new int[i + 2];
            for (int j = 0; j < posCounts.length; j++) {
                int posCount = posCounts[j];
                result += count(posCount, j, aChar, i);
            }

        }
        return result;
    }


    private int count(int posCount, int j, char aChar, int i) {

        if (aChar == 'A') {
            for (int k = j + 1; k <= i + 1; k++) {
                tmpPosCounts[k] += posCount;
            }
            return (i + 1 - j) * posCount;

        } else if (aChar == 'B') {
            for (int k = 0; k <= j; k++) {
                tmpPosCounts[k] += posCount;
            }
            return (j + 1) * posCount;
        } else {
            throw new RuntimeException("Oops");
        }

    }

}

System.out.println(new Counter().count("ABBABBABAB"));
        System.out.println(new Counter().count("ABBABBABABABBABBABAB"));
很快就出来了
这回是O(n^3)了

嗯嗯，仔细地看了一两位的实现代码，发现扫一眼确实是不够的呀 …… 两位的思路都还是不错的，抓住了最后一个字母在哪个位置这个关键，不过实现上就有问题：femto 最初的那个实现，枚举了所有插入的位置，这样那个 LastCharPoses 会增长得非常快，远远超过 O(n^3) 了；jkit 的实现也有类似问题，Pos 记录的个数增长同样太快了。不过 femto 最后给的那个优化算法很棒，严格说来应该算是新的算法了，而且确实达到了 O(n^3) 的复杂度。