[luogu*] CF9D How many trees? dp+计算树的总数

前言

传送门 :

思路

状态表示 ; f [ n ] [ h ] f[n][h] f[n][h]表示 n n n个节点,高度大于等于 h h h的数量

状态计算 f [ i ] [ j ] = ∑ f [ i − k ] [ j − 1 ] ∗ f [ k ] [ j − 1 ] f[i][j] = \sum f[i-k][j-1]*f[k][j-1] f[i][j]=∑f[i−k][j−1]∗f[k][j−1]

因此最后答案就是 f [ n ] [ n ] − f [ n ] [ h − 1 ] f[n][n] - f[n][h-1] f[n][n]−f[n][h−1]

CODE

int f[N][N];

void solve()
{	
	cin>>n>>m;
	//当前节点
	for(int i =0;i