LeetCode HOT100 - 不同的二叉搜索树

注意到 n 很小

每次选定根节点后，剩下的数据可以分成小于它和大于它（对应于左子树和右子树）两部分

每部分又是独立的子问题，所以用 dp

转移就是枚举左子树的大小（实际上就是枚举根节点元素）

这样是可行的，是因为我们并不关注具体元素是什么，我们只关注个数和相对大小关系

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);dp[1] = 1;dp[0] = 1;for (int i = 2; i <= n; i++) {for (int j = 0; j <= i - 1; j++) {dp[i] += dp[j] * dp[i - 1 - j];}}for (int i = 0; i <= n; i++) {cout << dp[i] << " \n"[i == n];}return dp[n];}
};