題目
給你一個(gè)整數(shù) n ，求恰由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的二叉搜索樹有多少種？返回滿足題意的二叉搜索樹的種數(shù)。
例：
輸入：n = 3
輸出：5
方法：動(dòng)態(tài)規(guī)劃
- dp[i] 記錄由 i 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 i 互不相同的二叉搜索樹的種數(shù)，初始均為 0
- 由 0 個(gè)節(jié)點(diǎn)組成的二叉搜索樹有一種，由 1 個(gè)節(jié)點(diǎn)組成的二叉搜索樹有一種
- 循環(huán)遍歷，記錄從由 2 個(gè)節(jié)點(diǎn)組成的二叉搜索樹到由 n 個(gè)節(jié)點(diǎn)組成的二叉搜索樹的種樹。因?yàn)楦?jié)點(diǎn)的值是不固定的，那么內(nèi)層循環(huán)的參數(shù) j 表示根節(jié)點(diǎn)的值，不同根節(jié)點(diǎn)產(chǎn)生的樹種和即為最后的二叉搜索樹的種數(shù)。而每個(gè)根節(jié)點(diǎn)所產(chǎn)生的二叉搜索樹的種樹，由其左子樹的種樹與右子樹的種樹的乘積得到
class Solution(object):
def numTrees(self, n):
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
