Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
思路：
要得到整条路径走完后的最大值，可以变相的看把最大值加到第一行的数，得到第一行的最大值，需要把第一行和第二行的某个最大值相加，而得到第二行的某个数的最大值，又需要把第二行的数据与第三行的最大值相加，层层递推吧。
程序代码如下
#include<stdio.h>
#include<math.h>
//最大值计算，算是一个递推的问题，从结果开始推，一直推到最底层
int max(int a,int b)
{
if (a> b) {
return a;
} else {
return b;
}
}
int main() {
int n,i,j,m,k;
int resultArr[100][100];
int result = 0;
scanf("%d\n",&n);
for(i=0; i<n; i++)
{
for(j = 0; j <= i; j ++)
{
int in;
scanf("%d",&in);
resultArr[i][j] = in;
}
}
for(m=n-2;m>=0;m--)
{
for(k = 0;k <= m;k ++)
{
resultArr[m][k]+=max(resultArr[m+1][k],resultArr[m+1][k+1]);
}
}
printf("%d\n",resultArr[0][0]);
return 0;
}
//PS:终于遇到一个喜欢的题目。。
