[LeetCode] 96. Unique Binary Search Trees

思路: 动态规划. 开辟一个长度为n + 1的数组, 将前两项初始化为1, 这两个是树为空树或只有一个根节点的情况. 剩下的从1到n每个数都可以作为根节点, 当任意节点i做根节点时, 所有小于i的节点都要在它左子树边, 大于i的节点都要在它的右子树边, 所以当i为根节点时, 它的总树数目就是它左子树的数量乘上右子树的数量.

int numTrees(int n) { int counts[n + 1] = {0}; counts[0] = counts[1] = 1; for (int i = 2; i <= n; i++) for (int j = 1; j <= i; j++) counts[i] += counts[j - 1] * counts[i - j]; return counts[n]; }