题目描述

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.

题目解析

我们可以发现，只需求出左、右子树各有多少种，二者相乘即为以 i 作为root时BST的总数。所以我们可以用动态规划来实现。当节点数为0个的时候，子树为0个，节点为1个的时候，子树为1个，节点数为2个的时候，子树为2个。当n>=3的时候，左右子树种类之积就是结果。所以我们只需要由下至上求解即可。

代码实现

 int numTrees(int n) { vector<int>num; num.push_back(1); for(int i=1; i<=n; i++) { num.push_back(0); if(i<3) { num[i]=i; } else{ for(int j=1;j<=i;j++) { num[i]+=num[j-1]*num[i-j]; } } } return num[n]; }