题目链接

思路:

  这个题一开始一点思路没有，感觉模拟的话是不太可能的，直接选择看题解，在看完题解后恍然大悟

  • 1 dp状态 `dp[i,j] //n个结点，m个叶子结点有多少种形态
  • 2 状态方程 dp[i,j] = dp[i,j] + dp[x][y] * dp[i - x - 1][j - y] (x < i && y <=j)
    也就是说我们不需要去模拟，只需要暴力跑到dp[i,j]时，从小到大枚举左子树结点和左子树叶子结点个数有多少种形态以及对应剩下的结点和叶子结点组成的右子树有多少种形态，利用排列组合的思想，累加即可

但是要注意，我们求相对应的右子树结点时是要i - 1，因为要去掉根节点

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 55;
const int mod = 1e9 + 7;

//dp[n,m]：n个结点，m个叶子结点有多少种形态
ll dp[maxn][maxn];

void Solve()
{
    dp[0][0] = dp[1][1] = 1;//没有结点和只有一个结点肯定都是只有一种情况
    for(int i = 1; i <= 50; i++){
        for(int j = 1; j <= i; j++){
            for(int x = 0; x < i; x++){
                for(int y = 0; y <= j; y++){
                    dp[i][j] = (dp[i][j] % mod + dp[x][y] % mod * dp[i - 1 - x][j - y] % mod) % mod;
                }
            }
        }
    }
}

int main()
{
    int n,m;
    Solve();
    while(cin>>n>>m){
        cout<<dp[n][m]<<endl;
    }
    return 0;
}