题解 | 二叉树的个数

class Solution {
public:
    /**
     这道题可以用递归的方式进行模拟，模拟选取根节点的过程，每层递归处理一个根节点的情况，分左右子树再递归，返回左右子树可能的乘积；
	但是可以发现，成树的多样性和数字本身大小没有关系，只与数的个数有关，所以可以记录不同节点数的树的多样性，由小至大树，即动态规划；
     */
    static const int mod = 1000000007;
    
    int numberOfTree(int n) {
        vector<long long> dp(n+1); //下标表示有多少节点
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; ++i){  //i表示有多少节点
            for(int j=1; j<=i; ++j){
                dp[i] += (dp[j-1]*dp[i-j])%mod;  //对乘积结果取模
                dp[i] %= mod;	//多加和结果取模
            }
        }

        return dp[n];
    }
};