这题我折腾了一个星期，真的好死心，一个多星期一直在查到底是哪里出了问题，从感觉上算法是没有错误的，而且能够拿90分，那问题到底出在哪里呢？这一题我反反复复得找，再看标程，对着看，终于昨晚上找到了，算法没有一点问题，实现上有问题，超过了int 的范围，所以数据就出现了错误，然后就OVER了。 题目的思路是这样的，f[i][j]代表i个节点构成j层的树的个数，那么dp方程就是f[i][j] = {2 f[k][j – 1] f[i – k – 1][l]}(l = 1….j – 2, k = 1..i – 2) {f[k][j – 1] f[i – k – 1][l]} (l == j – 1, k = 1…i – 2) 这个算法的优化： 其实不需要从1循环到n，或者什么的，因为树和题目的特殊性质，不需要完全枚举，比如说当i=7的时候就不可能构成一层的树，就没必要考虑，当i=7的时候至少是3层，怎么计算呢？当已知节点数，log2(i) + 1的是最少的层数，(i – 1) / 2 + 1 是最大的层数。 当已知层数i时，最少的节点数是i 2 – 1，每层都有两个，但第一层只有一个；最多为2^i – 1，所以时间的优化还可以。 代码实现如下: