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

?

示例 1：

輸入：n = 3

輸出：5

示例 2：

輸入：n = 1

輸出：1

這題需要想到動(dòng)態(tài)規(guī)劃；

假設(shè)n個(gè)節(jié)點(diǎn)存在二叉排序樹(shù)的個(gè)數(shù)是G(n)，令f(i)為以i為根的二叉搜索樹(shù)的個(gè)數(shù)

即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

n為根節(jié)點(diǎn)，當(dāng)i為根節(jié)點(diǎn)時(shí)，其左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為[1,2,3,...,i-1]，右子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為[i+1,i+2,...n]，所以當(dāng)i為根節(jié)點(diǎn)時(shí)，其左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為i-1個(gè)，右子樹(shù)節(jié)點(diǎn)為n-i，即f(i) = G(i-1)*G(n-i),

上面兩式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)

代碼如下：