[数据结构与算法]DP5 有多少个不同的二叉搜索树

描述

给定一个由节点值从 1 到 n 的 n 个节点。请问由多少种不同的方法用这 n 个节点构成互不相同的二叉搜索树。

输入描述：

仅一行输入一个正整数 n ，表示节点的数量。

输出描述：

输出组成不同二叉搜索树的方法数。

思路：
给定一个有序序列 1?n，为了构建出一棵二叉搜索树，我们可以遍历每个数字 i，将该数字作为树根，将1?(i?1) 序列作为左子树，将(i+1)?n 序列作为右子树。
接着我们可以按照同样的方式递归构建左子树和右子树。在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。
由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，我们可以想到使用动态规划来求解本题。

给定序列1?n，我们选择数字i作为根，则根为i的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，
对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树。
1.G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。
2.F(i,n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数(1≤i≤n)。

对于边界情况，当序列长度为 1（只有根）或为 0（空树）时，只有一种情况:G(0)=1,G(1)=1
G(n)=sum(G(j)*G(n-j-1))//0<=j<=n-1

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int n = 0;
	cin >> n;
	vector<int> G(n + 1);
	for (int i = 0; i <= n; ++i)
	{
		if (i == 0 || i == 1)
			G[i] = 1;
		else
		{
			for (int j = 0; j < i; j++)
			{
				G[i] += G[j] * G[i - j - 1];
			}

		}
	}
	cout << G[n];
	return 0;
}