优秀网站建设排名公司,做文章网站,做网站下载什么软件,wordpress theme 免费给你一个整数 n #xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种#xff1f;返回满足题意的二叉搜索树的种数。
示例 1#xff1a;
输入#xff1a;n 3 输出#xff1a;5 示例 2#xff1a;
输入#xff1a;n 1 输出#xff1a;…给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。
示例 1
输入n 3 输出5 示例 2
输入n 1 输出1
采用dp[i] 表示含有i个节点的二叉搜索树其中二叉搜索树由左子树和右子树以及根结点组成。其中dp[i]由含有i-j节点的左子树和j-1节点的右子树和一个根结点组成。所以dp[i]的构造形式由左右子树决定。
最优子结构 dp[i]
状态转移方程dp[i] (dp[i - j] * dp[j - 1])
int numTrees(int n) {int dp[20] {0};dp[0] 1;dp[1] 1;for (int i 2; i n; i) {for (int j 1; j i; j) {dp[i] (dp[i - j] * dp[j - 1]);}}return dp[n];
}
