Python3(3.5.2) 解法, 执行用时: 612ms, 内存消耗: 4212K, 提交时间: 2020-06-10 17:27:57

n,m=map(int,input().split())
# dp[i][j]：高度为i且结点数为j个的树的个数
dp=[[0 for i in range(n+5)] for i in range(m+5)]
# dp1[i][j]：高度小于等于i且结点数为j个的树的个数
dp1=[[0 for i in range(n+5)] for i in range(m+5)]
dp[1][1]=1
for i in range(2,m+1):
    for j in range(3,n+1,2):
        for k in range(1,j,2):
            # 第i层有j个的，是左右都是第i-1层，加起来有j-1个的
            dp[i][j]+=dp[i-1][k]*dp[i-1][j-1-k]
            # 加上左有i-1层，右小于i-1层，
            dp[i][j]+=dp[i-1][k]*dp1[i-2][j-1-k]
            # 和左小于i-1层，右有i-1层的和。
            dp[i][j]+=dp1[i-2][k]*dp[i-1][j-1-k]
            dp[i][j]%=9901
    for j in range(n+1):
        dp1[i-1][j]=dp1[i-2][j]+dp[i-1][j]
        dp1[i-1][j]%=9901
print((dp[m][n]+9901)%9901)

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 608K, 提交时间: 2019-08-25 14:27:04

#include<bits/stdc++.h> 
using namespace std;
int dp[210][110];
int main(){
	int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++)
	dp[1][i]=1;
    for(int t=1;t<=k;t++)
    for(int i=3;i<=n;i+=2)
    for(int j=1;j<i;j+=2)
    dp[i][t]=(dp[i][t]+dp[j][t-1]*dp[i-j-1][t-1])%9901;
    cout<<(dp[n][k]-dp[n][k-1]+9901)%9901<<"\n";
    return 0;
}

C++(clang++11) 解法, 执行用时: 11ms, 内存消耗: 480K, 提交时间: 2021-02-16 19:20:42

#include<bits/stdc++.h>
using namespace std;
int n,k;
int f[210][110];
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		f[1][i]=1;
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=k;j++){
			for(int kk=1;kk<=i-2;kk++){
				(f[i][j]+=f[kk][j-1]*f[i-kk-1][j-1])%=9901;
			}
		}
	}
	cout<<(f[n][k]-f[n][k-1]+9901)%9901;
}