本文基于https://leetcode.cn/problems/unique-binary-search-trees/solutions/550154/96-bu-tong-de-er-cha-sou-suo-shu-dong-ta-vn6x/
个人感觉博主部分内容讲得跳跃性较强
记录如下
正文
首先是dp数组的定义, 我觉得应该直接说明的是, dp[i] 意味着有i个节点的搜索树的数量
同时dp[0]我们在本题中人为定义为1(仅限本题)
其次是图片, 请看我用颜色记号额外标记的图片
可以发现N个节点的二叉搜索树, 除了根节点, 剩下的节点的拓扑关系是所有N-1个节点的搜索树的拓扑关系的并集
其中, 根节点的左右子树互相之间的变化有一定联系, 那就是节点个数之和为N-1
同时又具备一定的独立性, 当左子树的拓扑为A时, 右子树可以是a, b, c...
当左子树为B时, 右子树依旧可以是a, b, c...
因此除了根节点以外的子树部分, 他们的情况应当用乘法, 左子树的对应情况乘右子树的对应情况
这里说的对应情况指的是, 需要让左右子树节点和满足N-1这个约束条件
有点像高中的等比等差数列求和的感觉了
综上我们可以写出
dp[3] = 三个节点的搜索树个数 = 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树是2个节点的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有3个元素的搜索树数量就是dp[3]。
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
最后代码就是
#include<vector>
using namespace std;
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0]=1;
for(int i = 1; i <=n;++i){
for(int j = 1; j<=i;j++)
dp[i]+=dp[j-1]*dp[i-j];
}
return dp[n];
}
};