7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
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.
Your program is to write to standard output. The highest sum is written as an integer.
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5Sample Output
30
方法描述:从最底下一行开始,逐步向上相加,每次都选取最大的和数
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAX 105 5 6 int main() 7 { 8 int n; 9 int tri[MAX][MAX]; //存放三角形数据 10 int maxNum[MAX]; //存放每个子问题的最大数 11 int i,j; 12 scanf("%d",&n); 13 for (i=1; i<=n; i++) 14 for (j=1; j<=i; j++) 15 scanf("%d",&tri[i][j]); 16 for (i=1; i<=n; i++) //先将最底下一行存放进数组 17 maxNum[i] = tri[n][i]; 18 for (i=n; i>1; i--) 19 for (j=1; j<i; j++) 20 { //逐步向上一层相加,并将和最大的数存放进数组 21 if (maxNum[j]>maxNum[j+1]) 22 maxNum[j] += tri[i-1][j]; 23 else 24 maxNum[j] = maxNum[j+1]+tri[i-1][j]; 25 }
//最后,maxNum[1]即为结果 26 printf("%d",maxNum[1]); 27 return 0; 28 }