二叉树

import java.util.*;

public class Main{
    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        // dp[i][j]表示i个节点最大深度为j的树数量
        long[][] dp = new long[n+1][m+1];
        Arrays.fill(dp[0], 1);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                for(int k = 0; k < i; k++) {
                    // 左子树节点数为k，右子树节点数为i-k-1，且左右子树都要求小于等于j-1
                    dp[i][j] = (dp[i][j] + dp[k][j-1] * dp[i-k-1][j-1] % MOD) % MOD;
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n; // 节点个数
    int m; // 最大高度
    cin >> n >> m;
    
    // dp[i][j] 表示 i 个节点能够组成的高度不超过 j 的树的个数
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 0; i <= m; ++i) {
        dp[0][i] = 1;
    }
    
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            // 选取一个节点作为根节点
            // k 个节点作为左子树，i - k - 1 个节点作为右子树
            for(int k = 0; k < i; ++k) {
                dp[i][j] = (dp[i][j] + dp[k][j - 1] * dp[i - k - 1][j - 1] % MOD) % MOD;
            }
        }
    }
    
    cout << dp[n][m] << endl;
}

#include<bits/stdc++.h>
using namespace std;
const int ll = 1000000007;

int main(){
    int n, m;
    cin >> n >> m;
    //dp[i][j]:i个节点且高度不超过j的二叉树个数
    vector<vector<long>> dp(n + 1, vector<long>(m + 1, 0));
    //初始化dp[0][j] = 1, 即不同高度的空树都只有一种可能
    for(int j = 0; j <= m; j++){
        dp[0][j] = 1;
    }
    //其他dp[i][0]都为0
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            //k为左子树节点数，总共有i个节点， 故右子树有i - 1 - k个节点， i ~[0, i - 1]
            for(int k = 0; k < i; k++){
                //乘法原理，左右子树两两组合，左右子树高度减1
                dp[i][j] = (dp[i][j] + dp[k][j - 1] * dp[i - 1 - k][j - 1]) % ll;
            }
        }
    }
    cout << dp[n][m] << endl;
}

import sys
from functools import cache
from math import log2


@cache
def dfs(n: int, m: int) -> int:
    if n == 0:
        return 1
    if m < int(log2(n)) + 1:
        return 0
    acc = 0
    for k in range(n):
        acc += dfs(k, m - 1) * dfs(n - 1 - k, m - 1)
    return acc % e


n, m = map(int, input().split())
e = 10 ** 9 + 7
print(dfs(n, m))

import java.util.*;
import java.io.*;
public class Main {
    private static long[][] dp;
    private static  int m;
    private static  long mod = (long)1e9 + 7;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = null;
        while ((s = reader.readLine()) != null) {
            String[] s1 = s.split(" ");
            int n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);

            dp = new long[n + 1][m + 1];
            for (int i = 0; i <= n; i++) {
                Arrays.fill(dp[i], -1);
            }
            long res = highestNum(n,0);
            System.out.println(res);
        }

    }

    //左右节点数量,高度作为状态
    public static long highestNum(int treeNum, int high) {
        if (high > m) {
            return 0l;
        }
        if (treeNum == 0) {
            return 1l;
        }

        if (dp[treeNum][high] != -1l) {
            return dp[treeNum][high];
        }
        long ans = 0l;
        treeNum--;
        for (int i = 0; i <= treeNum; i++) {

            long left = highestNum(i, high + 1);
            long right = highestNum(treeNum - i, high + 1);
            ans = (ans +((left % mod) * (right % mod))) % mod;
        }
        treeNum++;
        dp[treeNum][high] = ans;
        return ans;

    }
}

import numpy as np
n=int(input())
m=int(input())
MOD=1e9+7 data=np.zeros([n+1,m+1],int)
data[0]=[1]*(m+1) for i in range(1,n+1): for j in range(1,m+1): for k in range(i):
            data[i][j]=(data[i][j]+data[k][j-1]*data[i-k-1][j-1] % MOD)%MOD print(data[i][j])

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

//n个节点，高度不超过m一共能组成多少棵BST
long long numofBST(int n, int m){
    vector<vector<long long> > dp(n+1, vector<long long>(m+1));
    for(int j = 0; j <= m; j++){
        dp[0][j] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k < i; k++){ //先用一个点构成root，左子树有k个，右子树有i-k-1个
                dp[i][j] = (dp[i][j] + dp[k][j-1] * dp[i-k-1][j-1] % MOD) % MOD;
            }
        }
    }
    return dp[n][m];
}

int main(){
    int n, m;
    cin >> n >> m;
    cout << numofBST(n, m);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
static const int mod = 1e9+7;
int main(){
    int n,m;
    while(cin>>n>>m){
        vector<vector<long>> dp(n+1,vector<long>(m+1));
        for(int i=0;i<=m;i++) dp[0][i] = 1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int k=0;k<=i-1;k++)
                    dp[i][j] = (dp[i][j] + dp[i-1-k][j-1]*dp[k][j-1]%mod)%mod;
        cout<<dp[n][m]<<endl;
    }
}

# i->节点数 j->二叉树的高度
# 卡特兰数列，状态转移方程应限制树的高度
# dp[i][j] = dp[i-(i-1)-1][j-1]*dp[(i-1)]dp[j-1] + ...
n, m = input().split()
n, m = int(n), int(m)
dp = [[0]*(m+1) for i in range(n+1)]
# 初始状态：结点数为零，只有一种方案
for j in range(m+1):
    dp[0][j] = 1
for i in range(1, n+1):
    for j in range(1, m+1):
        for re in range(i):
            # re + (i-re-1) = i-1
            dp[i][j] += dp[re][j-1]*dp[i-re-1][j-1]
print(dp[-1][-1]%(10**9+7))