跳转至

96 不同的搜索树

这道题正常人应该很难想到。。。

dp[i]表示节点1到节点i的搜索树个数

递推公式

\(dp[i] = \sum_{1}^{i}j为头节点的搜索树个数\)

j为头节点搜索树个数计算方法:dp[j - 1] * dp[i - j]

class Solution {
public:
    int numTrees(int n) {
        // dp[i]表示节点1到节点i的搜索树个数
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for(int i = 1;i <= n; i++){
            // 枚举头节点, j为头节点的值
            // 根据搜索树特性,j - 1为左子树的个数, i - j为右子树的个数
            for(int j = 1; j <= i; j++){
                // 递推公式
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};