首页 > 代码库 > 2.3.2 COW PEDIGREES 奶牛家谱
2.3.2 COW PEDIGREES 奶牛家谱
解题思路:
1.简单动态规划。基本思想是用小的二叉树去组成大的二叉树,最后输出dp[k][n]-dp[k-1][n]恰好就是要求的n个
点组成深度最多为k的方法数
2.设dp[i][j]表示j个点组成深度最多为i的二叉树的方法数,则动态规划公式为:
dp[i][j]=∑(dp[i-1][l]*dp[i-1][j-1-l])(1<=l<=j-2)
dp[i][1]=1
3.注意:点的个数总为奇数。
核心代码:
for(i=1;i<=k;i++) dp[i][1]=1; for(i=1;i<=k;i++) for(j=3;j<=n;j+=2) for(l=1;l<=j-2;l+=2) dp[i][j]=(dp[i][j]+dp[i-1][l]*dp[i-1][j-1-l])%9901;
2.3.2 COW PEDIGREES 奶牛家谱
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。