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

这题是这次 google 的 top coder 的 850 分例题，做过的同学先不要吱声：



嘿嘿，这就是你要解决的问题了。如果不嫌慢的话大可以穷举，不过这种解法拿出来那是显然不好意思和人打招呼的。事实上，如果设 AB 序列的长度为 n ，那么这个问题是可以做到 O(n^3) 的。

15 分钟内能够做出来，就有希望通过偶老板的算法考试了 ……

不知道对不对哦，我算出一个公式:
ABAB.. ，这个序列长度为n,  则解码为符合序列的个数为:
用数组替代上面ABA序列为a[n]
for(i=1... i=n-1)

（n+1)！/2 *  (a[i]-a[i-1] ==0？1：2)*/（n-i)
例如对于
ABA,用上面公式换算为;

4!/2 * 2/3 * 2/2=8

ABA明明只有5个阿，
cdab,cadb,cabd,acdb,acbd,
那来的8个？

AAA 就只有一个
  偶算错了。

题目中b和d看错乐，做错乐......用时完毕......go home

/**
   Counter.java
*/

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
* author     femto
* Date: 2005-8-14
*/
public class Counter {
    private List tmpLastCharPoses = new ArrayList();

    public int count(String s) {

        char[] chars = s.toCharArray();
        int result =0;
        List lastCharPoses;
        tmpLastCharPoses.add(new Integer(0));
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            lastCharPoses = tmpLastCharPoses;
            result = 0;
            tmpLastCharPoses = new ArrayList();
            for (Iterator it = lastCharPoses.iterator(); it.hasNext();) {
                Integer lastCharPos = (Integer) it.next();
                result += count(lastCharPos.intValue(), aChar, i);
            }
        }
        return result;
    }


    private int count(int lastCharPos, char aChar, int i) {
        if (aChar == 'A') {
            for (int j = lastCharPos + 1; j <= i + 1; j++) {
                tmpLastCharPoses.add(new Integer(j));
            }
            return i + 1 - lastCharPos;

        } else if (aChar == 'B') {
            for (int j = 0; j <= lastCharPos; j++) {
                tmpLastCharPoses.add(new Integer(j));
            }
            return lastCharPos + 1;
        } else {
            throw new RuntimeException("Oops");
        }

    }

}
/**
CounterTest.java
*/

import junit.framework.TestCase;

/**
* author     femto
* Date: 2005-8-14
*/
public class CounterTest extends TestCase {
    public void testCount() throws Exception {
        assertEquals(1, new Counter().count("A"));
        assertEquals(1, new Counter().count("B"));

        assertEquals(1, new Counter().count("AA"));
        assertEquals(2, new Counter().count("AB"));
        assertEquals(2, new Counter().count("BA"));
        assertEquals(1, new Counter().count("BB"));

        assertEquals(1, new Counter().count("AAA"));
        assertEquals(3, new Counter().count("AAB"));
        assertEquals(5, new Counter().count("ABA"));
        assertEquals(3, new Counter().count("ABB"));
        assertEquals(3, new Counter().count("BAA"));
        assertEquals(5, new Counter().count("BAB"));
        assertEquals(3, new Counter().count("BBA"));
        assertEquals(1, new Counter().count("BBB"));

        assertEquals(1, new Counter().count("AAAA"));
        assertEquals(4, new Counter().count("AAAB"));
        assertEquals(9, new Counter().count("AABA"));
        assertEquals(6, new Counter().count("AABB"));
        assertEquals(9, new Counter().count("ABAA"));
        assertEquals(16, new Counter().count("ABAB"));
        assertEquals(11, new Counter().count("ABBA"));
        assertEquals(4, new Counter().count("ABBB"));


    }
}

做出来鸟？不如推荐我去google?:)刚好最近在找工作~~
junit只测了前面4个字母的组合，应该是对的了:)
算法复杂度不知道是多少？不清楚这算不算穷举

是一道组合数学题，明显有公式，我都忘光了。

嘿嘿，femto 你倒是很有捷才呀。代码没有细看，不过看你的结果没错，而且思路也对，应该是没有问题了。

不错不错！:D