Open Douc1998 opened 1 year ago
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
输入：n = 3 输出：5
考点：动态规划，主要是需要弄懂 dp 数组的含义和递推公式。
参考：https://www.programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html function numTrees(n: number): number { // 构建 dp 数组：每个位置表示 n = index 时可以构建多少个不同的二叉搜索树 const dp: number[] = Array(n + 1).fill(0); // 初始化 dp[0] 和 dp[1] dp[0] = 1; dp[1] = 1; // 递推公式：以 j 为顶点的二叉树，左右分支可能各有几种，通过递推来实现 // dp[i] 就是累加 for(let i = 2; i <= n; i++){ for(let j = 1; j <= i; j++){ dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; };
参考：https://www.programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
function numTrees(n: number): number { // 构建 dp 数组：每个位置表示 n = index 时可以构建多少个不同的二叉搜索树 const dp: number[] = Array(n + 1).fill(0); // 初始化 dp[0] 和 dp[1] dp[0] = 1; dp[1] = 1; // 递推公式：以 j 为顶点的二叉树，左右分支可能各有几种，通过递推来实现 // dp[i] 就是累加 for(let i = 2; i <= n; i++){ for(let j = 1; j <= i; j++){ dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; };
题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例
解
考点：动态规划，主要是需要弄懂 dp 数组的含义和递推公式。