题解 | #二叉树#

题目：二叉树

题意

已知一颗二叉树有 n 个结点，问能构造出多少种高度不超过 m 的二叉树。

题解

• 对子树分治，左孩子依次为 0 ~ n-1 个结点，右孩子就是 n-1 ~ 0 这样去分治
• n=0，那就是空树，就是 1 种方案
• m=0，高度为 0，除了空树，不可能有高度为 0 的树，方案数为0
• 左右孩子一起分这 n-1 个结点，总数要相乘，乘法原理嘛

记忆化递归

int dp[55][55];
int fun(int n, int m)
{
    if(n==0)return 1;
    if(m==0)return 0;
    if(dp[n][m]!=-1)return dp[n][m];
    int ans=0;//要初始化
    for(int k=0;k<n;k++)//左右孩子一起分这 n-1 个结点，总数要相乘，乘法原理嘛
    {
        ans=(ans+(fun(k,m-1)*fun(n-k-1,m-1))%MOD)%MOD;
    }
    dp[n][m]=ans;
    return ans;
}

void solve(){
	cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j]=-1;
    cout<<fun(n,m);
}

二维dp

void solve(){
	cin>>n>>m;
	for(int i=0;i<=n;i++)dp[i][0]=0;
	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++)
			{
				dp[i][j]=(dp[i][j]+(dp[k][j-1]*dp[i-k-1][j-1])%MOD)%MOD;
			}
		}
	}
	cout<<dp[n][m];
}

一维dp

int dp3[55];
void solve(){
	cin>>n>>m;
	dp3[0]=1;
	for(int i=1;i<=n;i++)dp3[i]=0;
	//优先 从下到上，再从左到右 填数
	//因为 dp[i] 依赖于左上的那一列，第 m-1 列的 0~n
	for(int j=1;j<=m;j++)
	{
		for(int i=n;i>0;i--)
		{
			dp3[i]=0;
			for(int k=0;k<i;k++)
			{
				dp3[i]=(dp3[i]+(dp3[k]*dp3[i-k-1])%MOD)%MOD;
			}
		}
	}
	cout<<dp3[n];
}