Skip to content

14377: 【原4377】二叉搜索树的形状

题目

题目描述

author: Mighty_A 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4377

Description

给定一个整数$n$，有一棵$n$个节点的二叉搜索树，节点值依次为$1, 2,\dots, n$。求这棵二叉搜索树有多少种可能的形状。

  1. 由于输出结果较大，故要求结果对$1e9 + 7$取模后输出

  2. 不失一般性，如果$n = 0$，可能的形状为$1$

Input Format

一个整数$n$

Output Format

一个整数：运算结果对$1e9+7$取模后的值

Input Sample 1

1

Output Sample 1

1

Input Sample 2

3

Output Sample 2

5

Limits

$n \ge 0$

对于40%的数据，结果不会超过$1e9 + 7$

对于80%的数据，$n \le 100$

对于100%的数据，$n \le 1000$

ligongzzz's solution 

//
// Created by 谢哲 on 2021/4/13.
//

#include <iostream>
#include <vector>
using namespace std;

constexpr long long mod = 1e9+7;

vector<long long> dp_data;


long long dp(int l, int r) {
    if (dp_data[r-l]>=0) return dp_data[r-l];

    if (r-l==1) return 1;
    if (r==l) return 1;

    long long ans = 0;
    for (int i=l;i<r;++i) {
        long long ans_l = dp(l, i);
        long long ans_r = dp(i+1, r);
        ans = (ans+(ans_l*ans_r) % mod)%mod;
    }
    return dp_data[r-l] = ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    dp_data.resize(n+1, -1);

    cout<<dp(0, n);

    return 0;
}