# 工学1号馆

home

## Project Euler 18–Maximum path sum I

Wu Yudong    August 12, 2018     欧拉计划   612

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

3
7 4
2 4 6
8 5 9 3

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注意： 在这个问题中，由于只有16384条路径，通过尝试所有的路径来解决问题是可行的。但是，对于第67题，虽然是一道相同类型的题目，但是三角形将拥有一百行，此时暴力破解将不能解决，而需要一个更加聪明的办法！;o)

#include<stdio.h>

#define N 15
int main()
{
char t[5];
int s[N][N]={0};
FILE *f;
int i,j;
f = fopen("18.txt","r");
for (i = 0; i < N; i++) {
for (j = 0; j <= i; j++) {
fgets(t,4,f);
s[i][j] =atoi(t);
}
}
fclose(f);
for ( i = N-2; i >=0; i--) {
for ( j = 0; j <= i; j++) {
if (s[i+1][j] > s[i+1][j+1]) {
s[i][j]+=s[i+1][j];
} else {
s[i][j]+=s[i+1][j+1];
}
}
}
}