数字三角形――递归、递推、记忆化搜索

数字三角形

描述:
有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外没个数的左下方和右下方各有一个数。

问题：
从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHN0cm9uZz631s72o7o8L3N0cm9uZz48L3A+CjxwPiAgICAgICCyu8TRv7Sz9rTLzOLKx9K7uPa2r8ystcS+9rLfzsrM4qO6w7+0ztPQwb3W1tGh1PGhqqGq1/PPwrvy09LPwqGjyOe5+9PDu9jL3beox/Oz9sv509C1xL/JxNy1xMK3z9+jrL7Nv8nS1LTT1tDRobP21+7TxbXEwrfP36Gjtau6zc35s6PSu9H5o6y72Mvdt6i1xNCnwsrMq7XNo7rSu7j2brLjyv3X1sj9vcfQzrXEzerV+8K3z9/T0DJebsz1o6y1sW663LTzyrG72Mvdt6i1xMvZtsi9q8jDyMvO3reoyMzK3KGj0vK0y7G+zOLM1sLb08O13bnpo6y13c3GvLC8x9Lku6/L0cv3tcS3vbeoyrXP1qOsy+TIu7u509DG5Mv7tcS3vbeoo6y1q7TLyrHWu8zWwtvRp8+wsci9z8/gJiMyMDI4NDu1xNXivLjW1re9t6ihozxicj4KPC9wPgo8cD48YnI+CjwvcD4KPHA+PGJyPgo8L3A+CjxwPjxzdHJvbmc+1+7PyM/rtb21xMrHtd256cq1z9ajujwvc3Ryb25nPjwvcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">#include "stdio.h" #define maxn 100 int a[maxn][maxn],n; inline max(int x,int y) { return x>y x:y; } //递归计算实现 int d(int x,int y) { return a[x][y]+(x==n 0:max(d(x+1,y),d(x+1,y+1))); } int main() { while(~scanf("%d",&n)) { int i,j; for(i=1;i<=n;i++){ for(j=1;j<=i;j++) scanf("%d",&a[i][j]); } printf("max:%d\n",d(1,1)); } return 0; }虽然这样做是正确的，但时间效率太低，其原因在于重复计算。
例： 在下列计算中d(3,2)被重复调用

d(2,1) 的计算会调用--> d(3,1) , d(3,2)
d(2,2) 的计算会调用--> d(3,2) , d(3,3)

递推的实现：

#include "stdio.h"
#define maxn 100
int a[maxn][maxn],n;

inline max(int x,int y)
{
	return x>y x:y;	
}

//递推实现 
int d(int x,int y)
{
	int d[n][n],i,j; 
	for(j=1;j<=n;j++) d[n][j]=a[n][j];
	for(i=n-1;i>=1;i--){
		for(j=1;j<=i;j++)
			d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);
	}
	
	return d[x][y];
} 


int main()
{
	while(~scanf("%d",&n))	
	{
		int i,j;
		for(i=1;i<=n;i++){
			for(j=1;j<=i;j++)
				scanf("%d",&a[i][j]);
		}				
		printf("max:%d\n",d(1,1));							
	}
	return 0;
}

记忆化搜索实现：

#include "stdio.h"
#include "string.h" 
#define maxn 100
int a[maxn][maxn],n;
int d[maxn][maxn];	//记忆化搜索所使用的状态记忆数组 
inline max(int x,int y)
{
	return x>y x:y;	
}

/*
	记忆话搜索。程序分成两部分。首先  memset(d,-1,sizeof(d)); 把d全部初始化为-1， 
然后编写递归函数： 
*/ 
int distance(int i,int j)
{
	if(d[i][j]>=0) return d[i][j];
	return d[i][j]=a[i][j]+(i==n 0:max(distance(i+1,j),distance(i+1,j+1)));
} 
/*
	上述程序依然是递归的，但同时也把计算结果保存在数组d中。题目中说各个数都是非负的，因此
如果已经计算过某个d[i][j]，则它应是非负的，这样，只需把所有d初始化为-1，即可通过判断是否
d[i][j]>=0得知是否已经被计算过。 
*/ 


int main()
{
	while(~scanf("%d",&n))	
	{
		int i,j;
		for(i=1;i<=n;i++){
			for(j=1;j<=i;j++)
				scanf("%d",&a[i][j]);
		}
		memset(d,-1,sizeof(d));	//状态记忆化数组初始化 				
		printf("max:%d\n",distance(1,1));							
	}
	return 0;
}