导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-96.Unique Binary Search Trees

题目

Given n, how many structurally unique BST’s (binary search trees) that store values 1… n ?

For example,
Given n = 3, there are a total of 5 unique BST’s.

 1       3   3   2   1
  \     /   /    / \   \
   3   2   1    1  3   2
  /   /     \           \
 2   1       2          3

翻译

给出n,有多少种唯一的存储1到n的BST(搜索二叉树)?
例如,给出n=3,总共有5中唯一的BST。
 1       3   3   2   1
  \     /   /    / \   \
   3   2   1    1  3   2
  /   /     \           \
 2   1       2          3

假设n个元素,以k为根的BST数量为,由1到k-1组成的BST数量与k+1到n组成的BST数量的乘积,即C[k为根] = C[k - 1] * C[n - k]。
n个元素所有的BST即为以从1到n为根,每个BST数量的和。
利用动态规划,从1开始计算,一直到n,记录过程中每个C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int numTrees(int n) {
if (n <= 0) return 0;

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

参考:
http://www.blogjava.net/menglee/archive/2013/12/20/407801.html
http://www.tuicool.com/articles/IFZbAr