p96

发表于 | 分类于 |

LeetCode p96 Unique Binary Search Trees 题解

1.题目：

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

题意：

输入一个整数，输出这个整数能够有的BST的个数。

2.解题思路:

dp,取某个数为中间父节点，计算他左右节点可能的种类，相乘为所求。
用一个数组记录每个n对应的答案，避免重复的计算。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
public class Solution {
    public int numTrees(int n) {
		int ans = 0;
		int sum = 0;
		int[] list = new int[n + 1];
		if (n < 1)
			return ans;
		if (n < 3)
			return n;
		list[1] = 1;
		list[2] = 2;
		// System.out.println(n);
		// if (n==3) return 5;
		// int mid=n/2;
		return dp(list, n);

	}

	public int dp(int[] list, int n) {

		if (n == 0)
			return 1;

		if (list[n] != 0)
			return list[n];
		int ans = 0;
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			int mid = i;
			ans = dp(list, mid - 1) * dp(list, n - mid);//关系式
			sum = sum + ans;

		}
		list[n] = sum;
		return list[n];

	}
}

4.一些总结：