题目分析

有两个可变参数：节点个数n和最大高度m。可以发现求每棵树及其子树的方法类似只是参数数值不同，符合大问题转小问题，尝试递归解决

递归写法

// 记忆化搜索
vector<vector<int>> dp(n+1, m+1);
// 为了看得更直观没有取余
// 两个参数
// 含义：这棵树有n个节点，现在在H+1-m层，只有[1,H]层，所以m=0时，在H+1-0层，没有这种情况，返回0 
long long f(int n, int m){
// basecase
	// 节点为0则这层（这个节点）有1种可能返回1 
	if (n==0) return 1;
	// 超过层数没有可能，返回0 
	if (m==0) return 0;
// memory
  	// 加上记忆化搜索优化
	if (dp[n][m]!=-1)return dp[n][m];
// solve
	long long res = 0;
	// 有[0,n-1]个节点可能在一颗子树上，因为head占一个节点 
	for (int i = 0; i < n; i++){
      	// 加上左子树的为i个节点时构造可能，右子树同理
		res += f(i, m-1) * f(n-1-i, m-1);
    }
// return
	return dp[n][m] = res;
}

无注释版

vector<vector<int>> dp(n+1, m+1);
long long f(int n, int m){
	if (n==0) return 1;
	if (m==0) return 0;
	if (dp[n][m]!=-1)return dp[n][m];
	long long res = 0;
	for (int i = 0; i < n; i++){
		res += f(i, m-1) * f(n-1-i, m-1);
    }
	return dp[n][m] = res;
}

此时发现可变参数只有非常简单的两个：n 和 m，非常适合用动态规划优化

动态规划

把记忆优化过的递归转换过来即可，以下是时间复杂度O()最优解

long long f2(int n, int 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;
  	// 初始化本身就为0
  	// for (int i = 1; i <= n; j++)dp[i][0] = 0;
  
  	// 从第二层开始
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j--){
			for (int k = 0; k < i; k++){
				dp[i][j] += (dp[k][j]%mod * dp[j-k-1][j]%mod + mod) % mod;
			}
		}
	}
	return (dp[n][m]+mod)%mod;
}

又发现每一个m列的格子只依赖m-1列格子的dp值，所以dp表可以压缩成一维 ->

以下是最最最最最优解

long long f2(int n, int m){
  	// 依赖上一层m，所以dp表开的是n（一层m）
	vector<long long> dp(n+1);
  	// 虽然0高度，但0节点也算一种可能
	dp[0] = 1;
  	// 遍历顺序也得改变
	for (int i = 1; i <= m; i++){
      	// 倒序遍历，因为下面的k依赖的是上一层的1~j-1范围，倒序才能依次覆盖
		for (int j = n; j >= 1; j--){
          	// 初始化，覆盖上一层的值
			dp[j] = 0;
			for (int k = 0; k < j; k++){
				dp[j] += (dp[k] * dp[j-k-1] + mod) % mod;
			}
		}
	}
	return (dp[n]+mod)%mod;
}

战绩可查