Skip to main content

96. Unique Binary Search Trees

分析


Pasted image 20220430205219.png

题解

function numTrees(n: number): number {
const dp: number[] = []
dp[0] = 1
dp[1] = 1
dp[2] = 2

// dp[3] = dp[2] * dp[0] + dp[1] * dp[1]
for (let i = 3; i <= n; i++) {
const subMaxN = i - 1
dp[i] = 0
for (let j = 0; j <= subMaxN; j++) {
dp[i] += dp[j] * dp[subMaxN - j]
}
}

return dp[n]
};