算法步骤:
1.首先构造三个数组,第一个是存储三角形初始值的数组data[][];第二个是存储顶点到该点最大值的res[][]数组;第三个是存储该点上一个点的loc[][]数组。这里要对res[][]数组进行初始化-1;
2.按照三角形的层次结构,从上到下,从左到右依次计算res[][],对于每一个位置(i,j),找到res(i-1,j)和res(i-1,j-1)中较大的那个值,加上data[i][j],便得到了res[i][j];同时,在loc[][]中记录相应的前一个点。
3.在res[][]数组的最后一行找到最大值,该最大值便是目标最大值。之后利用loc[][]数组来进行回溯,输出整个路径。
实例以及代码
问题描述:编写一个程序,计算从顶部开始到底部某处的路径上传递的最大数字总和。路径上的每步只能沿对角线向左下或者右下滑动。
//res是存储最大值的数组,loc中存储的前一个点
int res[10][10],loc[10][10];
//处理输入数据
int Input(int data[][10]){
int n,i,j;
printf("三角形层数为:");
scanf("%d",&n);
printf("三角形元素值为:\n");
for(i=1;i<=n;i++)
for(j=0;j<i;j++)
scanf("%d",&data[i][j]);
return n;
}
//对res数组初始化
void Initial(int n){
int i,j;
for(i=1;i<=n;i++)
for(j=0;j<n;j++)
res[i][j]=-1;
}
//依次计算每一个位置的最大值
void DealWith(int n,int data[][10]){
int i,j,t1,t2;
res[1][0]=data[1][0];
for(i=2;i<=n;i++)
for(j=0;j<i;j++)
{
t1=0;t2=0;
if(res[i-1][j]>0)
t1=res[i-1][j];
if(j-1>=0&&res[i-1][j]>0)
t2=res[i-1][j-1];
if(t1>t2) //相比较,选大的
{
res[i][j]=t1+data[i][j];
loc[i][j]=j;
}
else
{
res[i][j]=t2+data[i][j];
loc[i][j]=j-1;
}
}
}
//找到res中最大的值
int Max(int n){
int i,max=0;
for(i=1;i<n;i++)
if(res[n][i]>res[n][max])
max=i;
return max;
}
//格式化输出
void Output(int n,int l,int data[][10]){
int i,a[10],k=0;
printf("最大为:%d\n",res[n][l]);
printf("路径为:");
for(i=n;i>0;i--)
{
a[k++]=data[i][l];
l=loc[i][l];
}
printf("%d",a[k-1]);
for(i=k-2;i>=0;i--)
printf("->%d",a[i]);
}
int main(){
int data[10][10];
int n,l;
n=Input(data);
Initial(n);
DealWith(n,data);
l=Max(n);
Output(n,l,data);
return 0;
}
运行结果: