96. 不同的二叉搜索树

题目

• 给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

例题

解题

• 动态规划：题解如上，分个数讨论，依次从1、2、3、4往上，在前者的基础上讨论现在的可能情况

---

代码

int numTrees(int n) {
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	int res = 0;
	vector<int>dp(n + 1, 0);
	//求dp[3]——— 02 11 20
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			dp[i] += dp[j] * dp[i - j - 1];
		}
	}
	return dp[n];
}

---

• 类似题型

22.括号的生成

题目

• 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

例题

• 输入：n = 3
• 输出：

代码

vector<string> generateParenthesis(int n) {
	if (n == 0) return { "" };
	if (n == 1)return { "()" };

	vector<vector<string>>dp(n + 1);
	dp[0] = { "" };
	dp[1] = { "()" };

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			for (string p : dp[j]) {     //左和右的不同组合，添加到vector中去，使用vector添加
				for (string q : dp[i - j - 1]) {
					string str = "(" + p + ")" + q;
					dp[i].push_back(str);
				}
			}
		}
	}
	return dp[n];
}