96. Unique Binary Search Trees
C++，讲一下思路。
- 设n个结点的树能组成bst个数为
dp(n)，以点i为根结点构成的BST数目为f(i)； - 根据以上假设，我们可以先得出
dp(0) = 0，dp(1) = 1，这是边界条件； - 因为bst的个数应该为以每个结点作为根结点能构成的bst数目的总和，则有
dp(n) = f(1) + f(2) + f(3) + ... + f(n)：$ \sum_{i=0}^{n}f(i) $ - 再来看下如何计算f(i)的值，每个结点构成的bst树数目实际上应该等于所有左子孙结点构成bst数目与所有右子孙结点构成bst数目的乘积，即
f(i) = dp(i-1) * dp(n-i)； - 所以最后公式就变成了
dp(n) = dp(0) * dp(n-1) + dp(1) * dp(n-2) + ... + dp(n-1) * dp(0)；即：$ dp(n)=\sum_{i=0}^{n}dp(i-1)*dp(n-i-1) $
用代码实现以上思路就行，递归+dp应该更好理解。。。
dp+递归版本：
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1, -1);
dp[1] = 1;
dp[0] = 1;
return (dp[n] = f(n, dp));
}
int f(int n, vector<int> &dp) {
if (dp[n] != -1) return dp[n];
else dp[n] = 0;
for (int j = 0; j < n; j++) {
int mul = 1;
if (dp[j] == -1) mul *= (dp[j] = f(j, dp));
else mul *= dp[j];
if (dp[n-j-1] == -1) mul *= (dp[n-j-1] = f(n-j-1, dp));
else mul *= dp[n-j-1];
dp[n] += mul;
}
return dp[n];
}
};
dp版本：
class Solution {
public:
int numTrees(int n) {
int dp[n + 1] = {0};
dp[1] = 1;
dp[0] = 1;
for (int i = 2; i <= n; i++)
for (int j = 0; j < i; j++)
dp[i] += dp[j] * dp[i - j - 1];
return dp[n];
}
};
