qwb与二叉树 算法分析 程序代码

原题:qwb与二叉树

对于一棵n个无编号节点,m个叶子的有根二叉树,有多少种形态呐?你能告诉他吗?

算法分析

http://blog.csdn.net/howardemily/article/details/72871260

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll dp[55][55];
int n,m;
ll dfs(int x, int y){
    ll &ans = dp[x][y];
    if(ans != -1) return ans;
    ans = 0;
    for(int i = 0; i <= x-1; i++)
        for(int j = 0; j <= i && j <= y; j++){
            ans += dfs(i,j) * dfs(x-i-1,y-j);
            ans %= mod;
        }
    return ans;
}
int main(){
    memset(dp,-1,sizeof(dp));
    dp[1][1] = 1;
    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[1][0] = 0;
    while(scanf("%d%d", &n, &m) == 2){
        printf("%lldn", dfs(n,m));
    }
    return 0;
}