96-不同的二叉搜索树

LeetCode 96. Unique Binary Search Trees

LeetCode-96

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3
Output: 5

method

对于一棵i个节点的搜索树，用j遍历每个可能的根节点，也就是1到i，当以j为根节点时，分成左右两边，左子树有j-1个节点，对应dp[j-1]种搜索树，右子树有i-j个节点，对应dp[i-j]种搜索树，所以状态转移方程是dp[i] = dp[j-1]*dp[i-j]，同时要累计dp[i]

空节点也是一棵树，所以初始化dp[0] = 1，后面用到乘法，也必须是1

int numTrees(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}