某一天,Zzq正在上数据结构课。老师在讲台上面讲着二叉树,zzq在下面发着呆。
突然zzq想到一个问题:对于一个n个节点,m个叶子的二叉树,有多少种形态呐?你能告诉他吗?
对于第一组样例的解释
每一组输入一行,两个非负数n,m(n<=50)意义如题目
每一行输出一个数,表示相应询问的答案取模1000000007
4 2 10 5
6 252
a取模b等于a%b,即a除以b的余数
#include<stdio.h> #include<string.h> const long long mod=1000000007; long long dp[55][55]; void init(){ memset(dp,0,sizeof(dp)); dp[1][1]=1; for(int i=2;i<=50;i++) for(int j=1;j<=50;j++){ dp[i][j]+=dp[i-1][j]*2; dp[i][j]%=mod; for(int k=1;k<=50&&i-k-1>=0;k++) for(int l=1;l<=50&&j-l>=0;l++){ dp[i][j]+=dp[k][l]*dp[i-k-1][j-l]; dp[i][j]%=mod; } } } int main(){ init(); int n,m; while(scanf("%d%d",&n,&m)!=EOF) printf("%lld\n",dp[n][m]); }
import java.util.*; /** dp[i][j]表示有i个节点,j个叶子节点的不同二叉树的形态。 对于dp[i][j],我们可以枚举根节点左子树的节点个数x和叶子节点个数y,将dp[x][y]∗dp[i−1−x][j−y]累加就可以得到dp[i][j]了。 因为对于一个单元格,其只依赖于其左上角区域的单元格(个数不确定,相对位置确定)。所以可以用从上到小,从左到右的动态规划,这样确保 计算每个单元格时,其左上角区域的单元格都是计算过的。 */ public class Main{ static int mod=1000000007; public static void main(String[] args){ long dp[][]=new long[60][60]; dp[0][0] = 1; dp[1][1] = 1; for(int i = 2; i <= 50; i ++) { for(int j = 1; j <= i - 1; j ++) { dp[i][j] = 0; for(int x = 0; x <= i - 1; x ++) { for(int y = 0; y <= x; y ++) { if(j - y < 0) continue; long sum = dp[x][y] * dp[i - 1 - x][j - y] % mod; dp[i][j] = (dp[i][j] + sum) % mod; } } } } Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int m=sc.nextInt(); int n=sc.nextInt(); System.out.println(dp[m][n]); } } }