题目

代码

/**
 * 本题是卡特兰数的变形(n个节点构成的二叉树共有多少种情况)
 * 1.二叉树不可旋转，即：左右子树交换视为不同的画法
 *  设fi表示一颗不考虑节点编号顺序的i个节点的二叉树的方案数量 (乘法原理)
 *      f n=f0*fn-1 + f1*fn-2 + f2*fn-3 +·······+ fn-2*f1 + fn-1*f0;
 *  其中fi * fn-1-i 表示在左子树放i个节点，在右子树放n-1-i个节点，构成的不同形状有fi*fn-i-1种;
 * 
 * 2.一个树如果形状相同，但是对应的节点编号不一样，也认为是两个不同的画法。
 *  接下来在考虑相同形状下，节点编号顺序不一样带来的影响，因为1号点已经确定，所以后面7个全排列即可，
 *  所以共有7！种
 *  
 *  所有总共方案书为7！*f8;
 *  
 *
 *  1.f8可以通过上述递推模型得出 (初值f0=1,f1=1)
 *  2.还可直接通过公式f8=C(2n,n)/n+1
 * @param args
 */
public class Main {
    static long[] dp=new long[9];
    static long fac=1;
    static long res=0;
    public static void main(String[] args) {
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=8;i++) {
            for(int j=0;j<i;j++) {
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        for(int i=1;i<=7;i++) {
             fac*=i;
        }
        res=fac*dp[8];
        System.out.println(res);
    }
}