AcWing 1645. 不同的二叉搜索树

题目

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

结果对 取模后输出。

输入格式

共一行，包含一个整数 。

输出格式

输出一个整数，表示对 取模后的结果。

数据范围

输入样例：

3

输出样例：

5

样例解释

当 时, 一共有 种不同结构的二叉搜索树:

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

题解

#include <iostream>
#define N 1010

const int MOD = 1e9 + 7;

using namespace std;

// f[i] 表示i个节点表示状态集合，属性是数量
// 转态转移: 左子树乘以右子树
int f[N];
int n;

int main()
{
    cin >> n;

    f[0] = 1;

    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j < i; ++ j) // 枚举左节点数量
            f[i] = (f[i] + (long long)f[j] * f[i - j - 1]) % MOD;

    cout << f[n] << endl;

    return 0;
}