【力扣】96. 不同的二叉搜索樹(shù)

給你一個(gè)整數(shù) n ，求恰由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的 二叉搜索樹(shù) 有多少種？返回滿(mǎn)足題意的二叉搜索樹(shù)的種數(shù)。

示例 1：

輸入：n = 3
輸出：5

示例 2：
輸入：n = 1
輸出：1

提示：
1 <= n <= 19

題解

• 確定 dp 數(shù)組以及下標(biāo)的含義
  dp[i] ： 1到 i 為節(jié)點(diǎn)組成的二叉搜索樹(shù)的個(gè)數(shù)為 dp[i]
  i 個(gè)不同元素節(jié)點(diǎn)組成的二叉搜索樹(shù)的個(gè)數(shù)為 dp[i]
• 確定遞推公式
  dp[3]，就是 元素1為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 + 元素2為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 + 元素3為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量
  元素1為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 = 右子樹(shù)有2個(gè)元素的搜索樹(shù)數(shù)量 * 左子樹(shù)有0個(gè)元素的搜索樹(shù)數(shù)量
  元素2為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 = 右子樹(shù)有1個(gè)元素的搜索樹(shù)數(shù)量 * 左子樹(shù)有1個(gè)元素的搜索樹(shù)數(shù)量
  元素3為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 = 右子樹(shù)有0個(gè)元素的搜索樹(shù)數(shù)量 * 左子樹(shù)有2個(gè)元素的搜索樹(shù)數(shù)量
  有2個(gè)元素的搜索樹(shù)數(shù)量就是 dp[2]。有1個(gè)元素的搜索樹(shù)數(shù)量就是 dp[1]。
  所以 dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
  

dp[i] += dp[以 1到i-1 為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量] * dp[以 i-(1到i-1) 為頭結(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)數(shù)量]

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為 j 為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量，i-j 為以 j 為頭結(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)數(shù)量。

• dp 數(shù)組如何初始化
  dp[0] = 1
• 確定遍歷順序
  節(jié)點(diǎn)數(shù)為 i 的狀態(tài)是依靠 i 之前節(jié)點(diǎn)數(shù)的狀態(tài)。
  那么遍歷 i 里面每一個(gè)數(shù)作為頭結(jié)點(diǎn)的狀態(tài)，用 j 來(lái)遍歷

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

• 舉例推導(dǎo) dp 數(shù)組（打印 dp 數(shù)組）

class Solution {public int numTrees(int n) {//初始化int[] dp = new int[n + 1];//初始化0個(gè)節(jié)點(diǎn)和1個(gè)節(jié)點(diǎn)的情況dp[0] = 1;// 遍歷for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {// dp 方程dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
}