卡特兰数
Peng's Blog 只记录和技术相关的东西

卡特兰数


卡特兰数公式

总的排列C(2n,n)
非法组合的可能有C(2n,n+1)
结果是卡特兰数公式,即C(2n,n)/(n+1)

常见例题

遇到下面这些,直接用卡特兰数的公式就可以了,非常简单!
enter description here

enter description here
enter description here

import java.util.*;
 
public class Parenthesis {
    public int countLegalWays(int n) {
        if(n<=0)
            return 0;
        // 总的排列C(2n,n)
        // 非法组合的可能有C(2n,n+1)
        // 结果是卡特兰数公式,即C(2n,n)/(n+1)
        int res=1;
        for(int i=2*n;i>=n+1;i--){
            res=res*i;
        }
        int di = 1;
        for(int j=1;j<=n;j++)
            di*=j;
        return res/di/(n+1);
    }
}

Comments

评论功能暂停使用,如需跟作者讨论请联系底部的GitHub