Description
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
Input
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。
Output
输出数据只有一个整数，表示计算出的最大值。
Sample Input
5
7
38
810
274 4
452 6 5
Sample Output
30
参考程序
#include <stdio.h>
#define LEN 100
struct Tri
{
int value;
int maxnum;
};
struct Tri Triangle[LEN+5][LEN+5];
void InputTriangle(int row)
{
int i,j;
for(i=1;i<=row;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&Triangle[i][j].value );
}
}
}
int GetMax(int a,int b)
{
return a>=b?a:b;
}
int GetMaxElement(int n)
{
int j;
int max=Triangle[n][1].maxnum;
for(j=2;j<=n;j++)
{
if(Triangle[n][j].maxnum>max)
{
max=Triangle[n][j].maxnum;
}
}
return max;
}
void GetSum(int n)
{
int i,j;
Triangle[1][1].maxnum=Triangle[1][1].value;
for(i=2;i<=n;i++)
{
for(j=1;j<=i;j++)
{
if(j==1)
{
Triangle[i][j].maxnum=Triangle[i][j].value+Triangle[i-1][j].maxnum;
}
else if(j<=i-1)
{
Triangle[i][j].maxnum=Triangle[i][j].value+GetMax(
Triangle[i-1][j-1].maxnum,Triangle[i-1][j].maxnum);
}
else
{
Triangle[i][j].maxnum=Triangle[i][j].value+Triangle[i-1][j-1].maxnum;
}
}
}
}
int main()
{
int n,result;
scanf("%d",&n);
InputTriangle(n);
GetSum(n);
result=GetMaxElement(n);
printf("%d\n",result);
return 0;
}
分析
本题是一个典型的多阶段决策问题，即求解的问题可以划分为一系列相互联系的阶段（步骤），在每个阶段都需要做出决策，且一个阶段决策的选择会影响下一阶段的决策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策使得整个过程达到最优。本题中考虑将三角形数阵转换为二维结构体数组，数组中每一个元素设置两个分量，一是数阵元素Triangle[i] [j].value，另一个是从数阵的顶点出发，走到Triangle[i][j]的最大权值，记为Triangle[i][j].maxnum。就其中一个点Triangle[i][j]考虑，到达该点的上一步可能是经过Triangle[i-1][j-1]到达的，也可能是经过Triangle[i-1][j]（假设下标不越界）到达的，现在为了能使得到达Triangle[i][j]累计的权值最大，即使得Triangle[i][j].maxnum最大，那么应该取Triangle[i-1][j-1].maxnum和Triangle[i-1][j].maxnum两者中的较大者。这样保证了决策中的某一步得到最优的结果。依次类推，可以按照此思路，求得Triangle[i-1][j-1].maxnum、Triangle[i-1][j].maxnum，……直到i=j=1的情形，而i=j=1正是递推的基础。这样对于数阵最后一行的每一个元素，若都求出了maxnum值，那么选取最大值即为本题的结果。
上面的思考过程是一个递归求解的思路，但是在编写程序时，我们将递归改为借助循环的递推，计算完一个值即保存下来，这样可以避免重复计算，这样解决了递归算法可能存在的重复运算导致时间复杂度高的弊端。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: