题目:
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
i(数量) | 种类 | 拆分 |
---|---|---|
i = 0 | 1 | |
i = 1 | 1 | |
i = 2 | 2 | 拆分节点 0+1+1 1+1+0 |
i = 3 | 5 | 拆分节点 0+1+dp[2] 1+1+1 dp[2]+1+0 其中 存在左节点或者右节点是右两个节点存在的可能只有1中 |
i = 4 | 14 | 拆分节点 0+1+dp[3] 1+1+dp[2] dp[2]+1+1 dp[3]+1+0 |
i = 5 | 42 | 拆分节点 0+1+dp[4] 1+1+dp[3] dp[2]+1+dp[2] dp[3]+1+1 dp[4]+1+0 |
dp[i] = dp[0]xdp[i-1] + (dp[1]xdp[i-2]) + ... + (dp[i-2]xdp[1]) + dp[i-1]*dp[0]
/**
* @param {number} n
* @return {number}
*/
var numTrees = function (n) {
let dp = Array(n + 1).fill(0)
dp[0] = 1
dp[1] = 1
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]
}
dp[i] = (dp[0]xdp[i-1])x2 + (dp[1]xdp[i-2])x2+(dp[2]xdp[i-3])x2 + ... + dp[n/2]x2
dp[i] = (dp[0]xdp[i-1] + dp[1]xdp[i-2] + dp[2]xdp[i-3] + ... + dp[n/2])/2
剩下的就交给数学推导吧,数学学不好代码都敲不了,泪崩
/**
* @param {number} n
* @return {number}
*/
var numTrees = function (n) {
let C = 1
for (let i = 0; i < n; ++i) {
C = (C * 2 * (2 * i + 1)) / (i + 2)
}
return C
}
使用递归改写动态规划
/**
* @param {number} n
* @return {number}
*/
var numTrees = function (n) {
let dp = Array(n + 1).fill(0)
function dpFn(x) {
if (x == 0 || x == 1) return (dp[x] = 1)
if (dp[x] > 0) return dp[x]
for (let i = 0; i < x; i++) {
dp[x] += dpFn(i) * dpFn(x - i - 1)
}
return dp[x]
}
return dpFn(n)
}