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

**  
 *   
 */  
package study.puzzle.sample1;   
  
import java.util.*;   
  
import junit.framework.TestCase;   
  
/**  
 * DOCUMENT ME!  
 *   
 * @author Godlikeme 2007-3-20  
 */  
public class Algorithm1Test extends TestCase {   
  
public void testCompute() throws Exception {   
        // assertEquals(,Algorithm.compute(""));   
        assertEquals(1, Algorithm.compute("A"));   
        assertEquals(1, Algorithm.compute("B"));   
        assertEquals(1, Algorithm.compute("AA"));   
        assertEquals(2, Algorithm.compute("AB"));   
        assertEquals(2, Algorithm.compute("BA"));   
        assertEquals(1, Algorithm.compute("BB"));   
        assertEquals(1, Algorithm.compute("AAA"));   
        assertEquals(3, Algorithm.compute("AAB"));   
        assertEquals(5, Algorithm.compute("ABA"));   
        assertEquals(3, Algorithm.compute("ABB"));   
        assertEquals(3, Algorithm.compute("BAA"));   
        assertEquals(5, Algorithm.compute("BAB"));   
        assertEquals(3, Algorithm.compute("BBA"));   
        assertEquals(1, Algorithm.compute("BBB"));   
        assertEquals(1, Algorithm.compute("AAAA"));   
        assertEquals(4, Algorithm.compute("AAAB"));   
        assertEquals(9, Algorithm.compute("AABA"));   
        assertEquals(6, Algorithm.compute("AABB"));   
        assertEquals(9, Algorithm.compute("ABAA"));   
        assertEquals(16, Algorithm.compute("ABAB"));   
        assertEquals(11, Algorithm.compute("ABBA"));   
        assertEquals(4, Algorithm.compute("ABBB"));   
        assertEquals(1, Algorithm.compute("AAAA"));   
        assertEquals(1, Algorithm.compute("BBBB"));   
        assertEquals(1, Algorithm.compute("BBBBBBBBBBBBBBBBB"));   
        assertEquals(1, Algorithm.compute("AAAAAAAAAAAAAAAAAAA"));   
        assertEquals(40932737,Algorithm.compute("AAAAABBAABBAAAAA"));   
        assertEquals(
				"77961101052771906279054003892476957478231542072323497761785202067698072199176691641558426633749048526359312876540673943650496621566256840081699153379703191232351264431848226789053430627229534974255679805774570964054601540378538438843097861227735459941778654699563308336374269767832682962176221580822415371619054678180592255250557108283479859134366715129117248030015013252495410340365746159653594812237689092688329502816565884197840680643248615557790386065427220993356310034524724459592233757880705810389624854250116398499956155395244214595828664435566808211796623188",
				Algorithm1
						.compute(
								"AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "AAAAAABBBBBBBBAAAAAAAAABBBBBBBBAAAAAAAAABBBBBB"
										+ "").toString());

    }}   
  
/**  
 *   
 * 假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m  
 * 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5  
 * 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。  
 * 现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序： 如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A  
 * （After），否则序列的第一个字母就是 B （Before）； 如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；  
 * 如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。 这规则甚是简单，不过有个问题就是同一个 AB  
 * 序列，可能有多个字符串都与之相符，比方说序列“ABA”，就有“acdb”、“cadb”等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。  
 * 那么现在问题来了：给你一个这样的 * AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？  
 * 注意，只要求个数，不要求枚举所有的字符串。  
 *   
 */  




abstract class Algorithm1 {
	public static BigDecimal compute(String sequenceStr) {
		matrix = new BigDecimal[sequenceStr.length()][sequenceStr.length()];
		return Algorithm1.calcPossible(sequenceStr, 0, 0);
	}

	static BigDecimal[][] matrix;// a memory matrix for fast calc;

	private static BigDecimal calcPossible(String sequenceStr, int left,
			int right) {
		if (sequenceStr.length() == 1) {
			if (sequenceStr.equalsIgnoreCase("A"))
				return new BigDecimal(right + 1);
			else if (sequenceStr.equalsIgnoreCase("B"))
				return new BigDecimal(left + 1);
		}

		if (sequenceStr.substring(0, 1).equalsIgnoreCase("A")) {
			if (matrix[left][right] != null)
				return matrix[left][right];

			BigDecimal result = new BigDecimal(0);
			for (int i = 0; i <= right; i++) {
				result=result.add(calcPossible(sequenceStr.substring(1), left + i + 1,
						right - i));
			}
			matrix[left][right] = result;
			return result;
		} else if (sequenceStr.substring(0, 1).equalsIgnoreCase("B")) {
			if (matrix[right][left] != null)
				return matrix[right][left];
			BigDecimal result = new BigDecimal(0);
			for (int i = 0; i <= left; i++) {
				result=result.add(calcPossible(sequenceStr.substring(1), left - i,
						right + i + 1));
			}
			matrix[right][left] = result;
			return result;
		} else {
			throw new IllegalArgumentException();
		}
	}
}

最后版本，7秒。