网站后台管理员怎么做,wordpress动漫,淘宝客网站模板,正规网站优化公司题目 给你一个整数 n #xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种#xff1f;返回满足题意的二叉搜索树的种数。 示例 1#xff1a; 输入#xff1a;n 3 输出#xff1a;5 示例 2#xff1a; 输入#xff1a;n 1 输出#xff1…题目 给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 示例 1 输入n 3 输出5 示例 2 输入n 1 输出1
解题思路 本题首先得找到规律通过推演可以发现存在递推关系用dp[i]表示数字i可以表示成dp[i]种搜索二叉树如dp[3]dp[0]*dp[2] dp[1]*dp[1] dp[2]dp[0]. 初始化dp[0]1,因为空树是搜索二叉树初始化dp[1]1.
代码实现
class Solution {
public:int numTrees(int n) {vectorint dp(n1, 0);dp[0] 1;dp[1] 1;for (int i 2; i n; i) {for (int j 1; j i; j) {dp[i] dp[j-1] * dp[i-j];}}return dp[n];}
};
