[代碼元]平衡二叉樹-創(chuàng)新互聯(lián)

題目描述
平衡二叉樹(AVL樹），是指左右子樹高度差至多為1的二叉樹，并且該樹的左右兩個(gè)子樹也均為AVL樹。 現(xiàn)在問題來了，給定AVL樹的節(jié)點(diǎn)個(gè)數(shù)n，求有多少種形態(tài)的AVL樹恰好有n個(gè)節(jié)點(diǎn)。
輸入描述
一行一個(gè)整數(shù)T(T≤2000)表示數(shù)據(jù)組數(shù)
T行, 每行一個(gè)整數(shù)n(n≤2000)
輸出描述
每行一個(gè)數(shù)字表示結(jié)果，由于結(jié)果巨大，輸出它對(duì)109+7取余數(shù)的結(jié)果。
輸入樣例
1
10
輸出樣例
60

創(chuàng)新互聯(lián)公司的客戶來自各行各業(yè)，為了共同目標(biāo)，我們?cè)诠ぷ魃厦芮信浜?，從?chuàng)業(yè)型小企業(yè)到企事業(yè)單位，感謝他們對(duì)我們的要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。專業(yè)領(lǐng)域包括成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、電商網(wǎng)站開發(fā)、微信營銷、系統(tǒng)平臺(tái)開發(fā)。

分析：

一棵樹是平衡二叉樹，其左子樹有子樹滿足同樣性質(zhì)。
性質(zhì)：左右子樹的高度差最多為1
則我們可以推導(dǎo)出樹與他的左右子樹的關(guān)系。
設(shè)dp[i][j]表示有i個(gè)節(jié)點(diǎn)，高度為j時(shí)候的方案數(shù)。
顯然當(dāng)0個(gè)結(jié)點(diǎn)時(shí)，算一個(gè)方案，只有一個(gè)節(jié)點(diǎn)時(shí)也算一個(gè)方案。
即dp[0][0]=dp[1][1]= 1
狀態(tài)轉(zhuǎn)移方程課表示為如下：
左右子樹同樣高：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]
其中節(jié)點(diǎn)的關(guān)系應(yīng)該為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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：[代碼元]平衡二叉樹-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article32/dpdosc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、品牌網(wǎng)站建設(shè)、域名注冊(cè)、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)