leetcode 96 不同的二叉搜索树

原题传送门—>>

题目描述：

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

-输入：3
-输出：5
-解释：
-以下 5 种不同结构的二叉搜索树：
-

• 1 3 3 2 1
• \ / / / \ \
• 3 2 1 1 3 2
• / / \ \
• 2 1 2 3

简单动规。
设dp[n]存储着n个结点共能组成多少不同的树。
以n = 5为例：
5个结点标记为1~5，取i号结点为根，则其左右子树分别有i-1、 5-i个结点。则共能生成dp[i-1] * dp[5-i]个结点

• dp[5] = dp[0] dp[4] + dp[1] dp[3] + dp[2] dp[2] + dp[3] dp[1] + dp[4] * dp[0]

class Solution {
public:
    int numTrees(int n) {
    int * dp = new int[100];
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        int sum = 0;
        for(int j = 1; j <= i; ++j)
        {
            sum += dp[j - 1] * dp[i - j];
        }
        dp[i] = sum;
    }
        int ans = dp[n];
        delete []dp;
        return ans;
    }
};