【动态规划：96. 不同的二叉搜索树】刷题记录

leetcode题目链接

题目：

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？
返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5

示例 2：
输入：n = 1
输出：1
提示：1 <= n <= 19

1、确定dp数组以及下标的含义

dp[i] 表示 1 到 i 可以组成的互不相同二叉搜索树的种类。

2、确定递推公式

这个题目有些抽象，可以举例推导来找出递推关系。

n = 1 时，只有 1 种，dp[1] = 1。

n = 2 时，1、2 能组成的不同的二叉搜索数有下列 2 种 dp[2] = 2。

n = 3 时，1、2、3 能组成的不同的二叉搜索数有下列 5 种。

让每个数都做一次根节点，当 1 做根节点时，左子树只有为空这 1 种情况，右子树有 2 种情况；当 2 做根节点时，左子树只有 1 种情况，右子树也只有 1 种情况；当 3 做根节点时，左子树有 2 种情况，右子树只有 1 种情况。

在二叉搜索树中，一个节点的左右孩子还是一个二叉搜索树。

不难发现，1 做根节点时，右子树的那 2 种情况其实就是求 2 和 3 能组成的二叉搜索树有多少种，也就是 dp[2] 的值，左子树为空，空也可以看成是 1 种情况，也就是说 dp[0] = 1，那么 1 做根节点时一共有 dp[0] × dp[2] = 2 种情况；2 做根节点时，左右子树各有 1 个节点，那么就是 dp[1] × dp[1] = 1 种情况；3 做根节点时有 dp[2] × dp[0] = 2 种情况；所以当 n = 3 时，一共有 dp[0] × dp[2] + dp[0] × dp[2] + dp[0] × dp[2] = 5 种。

归纳一下，可以得出：

dp[i] += dp[j] * dp[(i - 1) - j];

3、dp数组如何初始化

dp[0] = 1，dp[0] 不在题目要求范围内，为了方便计算，我们定义 0 个节点时为 1 种情况。

4、确定遍历顺序

外层循环从左向右遍历 dp 数组，内层循环是求 dp[i] 的计算过程，j 表示左子树节点个数，(i - 1) - j 表示右子树节点个数。

for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[(i - 1) - j]; } }

5、举例推导dp数组

可以尝试计算 dp[4] ，就不在此赘述了。

class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[(i - 1) - j]; } } return dp[n]; } }