题解 | 二叉树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const static ll mod=1000000007;
int n,m;
ll dp[51];
int main() {
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>n>>m;
    dp[0]=1;
    //先枚举列，因为j层是依赖于j-1层去产生的
    for(int j=1;j<=m;j++){
        //为什么需要从底至顶更新？
        //那是因为多的节点数量依赖于少的节点数量生成，如果相反的话就会覆盖掉原来的值
        for(int i=n;i>=1;i--){
            dp[i]=0;//一定记得要更新当前的节点信息
            //对于这道题是不依赖于原本的位置的信息的，不然你甚至还需要用一个变量去存取当前待更新节点的原信息
            for(int k=0;k<i;k++){
                dp[i]=(dp[i]+(dp[k]*dp[i-1-k])%mod)%mod;
            }
        }
    }
    cout<<dp[n]<<endl;
    return EXIT_SUCCESS;
}