任務(wù)描述

本關(guān)任務(wù)：編寫用動態(tài)規(guī)劃解決數(shù)塔問題。

相關(guān)知識

為了完成本關(guān)任務(wù)，你需要掌握：動態(tài)規(guī)劃。

編程要求

求上圖從頂層到頂層的一個路徑，使路徑上的數(shù)字和最大。要求輸出最大的數(shù)字和max和數(shù)值和最大的路徑。

解題思路：

原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型變量n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲成如下的下三角陣:?

1. 9
2. 12 15
3. 10 6 8
4. 2 18 9 5
5. 19 7 10 4 16

測試輸入：

1. 5
2. 9
3. 12 15
4. 10 6 8
5. 2 18 9 5
6. 19 7 10 4 16

輸出示例：文章來源地址http://www.zghlxwxcb.cn/news/detail-532566.html

1. max=59
2. 數(shù)值和最大的路徑是：9->12->10->18->10

#include <stdio.h> 

/********** Begin **********/
#define MAX(a,b)((a) > (b) ? (a) : (b))//宏定義
int main() {
	int a[50][50][4];    
    a[1][1][1]=9;
    a[2][1][1]=12, a[2][2][1]=15;
    a[3][1][1]=10, a[3][2][1]=6,  a[3][3][1]=8;
    a[4][1][1]=2,  a[4][2][1]=18, a[4][3][1]=9,  a[4][4][1]=5;
    a[5][1][1]=19, a[5][2][1]=7,  a[5][3][1]=10, a[5][4][1]=4, a[5][5][1]=16; 
	int dp[50][50];
	int i,j,num[50];
	int g,h,e;
	//把第5行數(shù)據(jù)放入dp[5][]中 
	for(j=1;j<=5;j++) {
		dp[5][j] = a[5][j][1]; 
	}
	//使用動態(tài)規(guī)劃尋找出最大路徑和 
	for(i=4;i>=1;i--) {
		for(j=1;j<=i+1;j++){
			dp[i][j] = MAX(dp[i+1][j],dp[i+1][j+1]) + a[i][j][1];
		}	
	}
	//找出n-2前所有路徑值 
	num[4] = dp[4][1];
	for(i=4;i>=1;i--) {
		for(j=1;j<=i;j++) {
			num[i] = MAX(num[i],dp[i][j]);
			//找出n-1行經(jīng)過路徑的值 
			if(dp[i][j] == 28) {
//				printf("i=%d\n",i);
//				printf("j=%d\n",j);
				g = i;
				h = j;
//				printf("%d\n",a[4][2][1]); 
//				printf("%d\n",a[5][3][1]); 
			}
		}
	}
	//找出n行經(jīng)過路徑的值
	for(j=1;j<=5;j++) {
			if(a[g][h][1] + a[5][j][1] == 28) {
				e = j;
			}
	}
	//輸出最大路徑和 
	printf("max=%d\n",dp[1][1]);
	//遍歷輸出各行路徑值 
	printf("數(shù)值和最大的路徑是："); 
	for(i=1;i<=5;i++) {
		if(i <= 3) {
			printf("%d->",num[i]-num[i+1]);
		} else if(i==4) {
			num[4] = a[g][h][1];
			printf("%d->",num[i]);
		} else if(i==5) {
			num[5] = a[5][e][1];
			printf("%d\n",num[i]);
			}
	}
    return 0;
}
/********** End **********/

到了這里，關(guān)于動態(tài)規(guī)劃 第1關(guān)：數(shù)塔問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！