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

主要是为了先实现，没怎么优化。用到太多string ,bigdecimal操作，写成primitive type会快很多，性能都消耗再创建对象上了。

我感觉这个事情应该用快速排序算法解决

最终总要用对象的。ruby也要用BigNum的。

顺便劝一下老榆树：不要什么东西都用让人发指的c++。对一个研究算法的严肃学者来说，死抠一个个的指针操作，移位算法，raii, stl标准库都应该属于标准的不务正业吧？

因此还是用ruby吧。代码容易写，也容易读。

是的，对象总是要用，只是在代码里没看到才这么说。
可以自己实现一个int[] 代替bigdecimal，那就比较麻烦了。
反对嘲笑c++。
动态语言能力matlab比ruby强。

ruby里面everything is object呀。当然用对象了。

那个，matlab比ruby强就能说明c++不该嘲笑？拿c++, java这种冬冬写算法不累呀？

对了，欢迎贴一个matlab的代码来实现这个算法，看看是否比ruby的好看。

ruby:
probs = Array.new(input.length+1)
matlab:
matrix =zeros

ruby:
for i in 0...input.length  
matlab:
for i = 0:length(input)


ruby:
save, probs[j] = probs[j], probs[j-1]+save  
matlab:
matrix(i,j)=sum(matrix(i-1,0:j-1))

ruby:
probs.inject(0){|sum,i|sum+i}
matlab:
sum(matrix(i,:))

没啥大区别。“强”也不在这上头。




一样。


ruby那个是O(1)的，你这个matlab版是O(n)的；ruby那个只有一个一维数组，没有matrix。没可比性。




也就这个稍微有点意义。但是这个算法的肉也不在这个sum上。


最后，麻烦写一个完整的算法啦。我对单纯比哪个语法更性感没兴趣。

我要的就是：简单，直观，没有boiler-plate code，直接描述算法本身，写出来类似伪码或者自然语言。

还有，如果matlab的某些函数自动实现某些算法，除非这个算法不是这个问题的关键（比如最后这个sum），否则不许用的。————如果问题是实现快排，你总不能直接调用quicksort库函数吧？

写错了，应该是
matrix(i,j)=matrix(i-1,j)+matrix(i,j-1)

随便比较下吧，n>5年不玩，不太熟了。

空间复杂度不如ruby那个。ruby那个是O(n)，你这个是O(n^2)

把ruby的实现翻译成java了。运行那个n=389花了0.08秒。比ruby慢了4倍。

看来BigInteger比ruby的BigNum慢不少啊。

public class Aba {
  public static BigInteger count(String input) {
    BigInteger[] probs = new BigInteger[input.length()+1];
    probs[0] = BigInteger.ONE;
    for(int i=0; i<input.length(); i++){
      if(input.charAt(i)=='A') {
        BigInteger save = probs[0];
        probs[0] = BigInteger.ZERO;
        for(int j=1; j<=i+1; j++) {
          BigInteger tmp = save;
          save = probs[j];
          probs[j] = probs[j-1].add(tmp);
        }
      }
      else {
        probs[i+1] = BigInteger.ZERO;
        for(int j=i; j>=0; j--) {
          probs[j] = probs[j].add(probs[j+1]);
        }
      }
    }
    return sum(probs);
  }
  static BigInteger sum(BigInteger... vals) {
    BigInteger result = BigInteger.ZERO;
    for(BigInteger val:vals) {
      result = result.add(val);
    }
    return result;
  }
}