189 8069 5689
题目描述
平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。 现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。
输入描述
一行一个整数T(T≤2000)表示数据组数
T行, 每行一个整数n(n≤2000)
输出描述
每行一个数字表示结果，由于结果巨大，输出它对109+7取余数的结果。
输入样例
1
10
输出样例
60创新互联公司的客户来自各行各业，为了共同目标，我们在工作上密切配合，从创业型小企业到企事业单位，感谢他们对我们的要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。专业领域包括成都网站设计、网站建设、电商网站开发、微信营销、系统平台开发。
分析：
一棵树是平衡二叉树，其左子树有子树满足同样性质。
性质：左右子树的高度差最多为1
则我们可以推导出树与他的左右子树的关系。
设dp[i][j]表示有i个节点，高度为j时候的方案数。
显然当0个结点时，算一个方案，只有一个节点时也算一个方案。
即dp[0][0]=dp[1][1]= 1
状态转移方程课表示为如下：
左右子树同样高：dp[i][j]=dp[L][j - 1]+dp[R][j - 1]
左子树高右子树低：dp[i][j]=dp[L][j - 1]+dp[R][j - 2]
左子树低右子树高：dp[i][j]=dp[L][j - 2]+dp[R][j - 1]
其中节点的关系应该为i = L + R + 1
代码：
#includeusing namespace std;
const int N = 2010, mod = 1e9 + 7;
int n;
int dp[N][N];
int main()
{dp[0][0] = dp[1][1] = 1;
for (int i = 2; i<= 2000; i ++ )
{for (int j = 2; j<= 20; j ++ )
{ for (int l = 0; l< i; l ++ )
{ int r = i - 1 - l;
dp[i][j] = (dp[i][j] + (long long)dp[l][j - 1] * dp[r][j - 1] % mod) % mod;
dp[i][j] = (dp[i][j] + (long long)dp[l][j - 2] * dp[r][j - 1] % mod) % mod;
dp[i][j] = (dp[i][j] + (long long)dp[l][j - 1] * dp[r][j - 2] % mod) % mod;
}
}
}
// for (int i = 0; i<= 20; i ++ )
// {// for (int j = 0; j<= 15; j ++ )
// printf("cnt = %d, h = %d, val = %d\n", i, j,dp[i][j]);
// }
int t;
cin >>t;
while (t -- )
{scanf("%d", &n);
int ans = 0;
for (int i = 0; i<= 20; i ++ )
ans = (ans + dp[n][i]) % mod;
printf("%d\n", ans);
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧