LeetCode题目：Unique Binary Search Trees，一维动态规划

By | 2012 年 11 月 1 日

Sigma(左边的子树可能状态 * 右边子树可能状态) = 当前个数的nodes形成的BST总数。

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
```

```class Solution {
public:
int numTrees(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 1) return n;
//ways[i] rep. the number of ways with i nodes
int *ways = new int[n + 1];
ways[0] = 1;
ways[1] = 1;
for(int i = 2 ; i <= n; ++i) {
ways[i] = 0;
for(int left = 0; left < i; ++ left) {
//with number of left noeds in the left sub-tree
int lways = ways[left];
int rways = ways[i - left - 1];
ways[i] += lways * rways;
}
}
int ret = ways[n];
delete [] ways;
return ret;
}
};
```

6 thoughts on “LeetCode题目：Unique Binary Search Trees，一维动态规划”

1. uniEagle Post author

that’s much safer, but not needed in this situation, because ways is a local variable, and the next line after

`delete [] ways;`

is return.

1. Jerry

Great post! Not familiar with C++ semantics, but should it be “delete[] ways” instead of “delete ways”?

1. uniEagle Post author

Oh, you are right, “delete aPointer” will delete just the space by this pointer, but not the whole array.