96. Unique Binary Search Trees
2019-04-20 本文已影响0人
majinliang123
这道题使用动态规划解决
对于1...n的节点,我们从中挑出一个节点 i (1 <= i <=n)作为根节点。在这种情况下,所有的情况的总数是1...i-1和i+1...n的乘积,G(n) = G(i -1) * G(n - i)
在给定n的情况下,结果是遍历i从1到n的结果的总和。G(n) = G(0)G(n-1) + ...+G(i -1) * G(n - i) + ... G(n-1)G(0)
这个我们用脑子想想就知道
G(0) = 1;
G(1) = 1;
我们从n=2开始,一步步往后算。代码如下。
class Solution {
public int numTrees(int n) {
int[] data = new int[n + 1];
data[0] = 1;
data[1] = 1;
for(int i = 2; i <= n; i++){
int current = 0;
for(int j = 1; j <= i; j++){
current += data[j - 1] * data[i - j];
}
data[i] = current;
}
return data[n];
}
}