数字三角——递归、递归、内存搜索

数字三角

叙述性说明:
         有一个非负整数三角，第一行中只有一个号码，的左下方和右下方各有一个数。

问题：
         从第一行的数開始。每次能够往左下或右下走一格。直到走到最下行，把沿途经过的数所有加起来。

怎样走才干使得这个和尽量大？
数字三角——递归、递归、内存搜索

分析：

不难看出此题是一个动态的决策问题：每次有两种选择——左下或右下。

假设用回溯法求出全部的可能的路线，就能够从中选出最优的路线。但和往常一样，回溯法的效率太低：一个n层数字三角形的完整路线有2^n条。当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
",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)

递推的实现：

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
",d(1,1));							
	}
	return 0;
}

记忆化搜索实现：

数字三角——递归、递归、内存搜索

数字三角

相关推荐