Project Euler——Problem 18

daybreakcx posted @ 2009年7月21日 04:16 in Prject Euler , 1172 阅读

原题与答案：

Problem 18

31 May 2002

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 5
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)

Answer:1074

分析与解答：

这个是传说中的数字三角形，是利用动态规划的一个经典题目，题目的意思是求从顶端到底部的一条路径，使得路经的数字的和最大，而路径则是可以从上往下走到其左下或者右下的临近数字。思路最直接的是从上往下执行，但是有一种更好的方法求得，现在介绍这种方法，假设 a[i][j] 表示以第i行j列为顶点的三角形顶点到底边的最大路径值。对于底边的某个数字，其的最优值必然是本身，那么对于中间的值，我们可以得到动态规划方程： $a[i][j]=maxn\{a[i+1][j],a[i+1][j+1]\}(1\leq i \leq n,1\leq j \leq i)$ 。我们最后的目标就是得到顶端的值。当然这个题目如果用这种方式就免不了要先把数字先全部读入结束，如果用另一种方法的话，可以利用滚动数组来减少空间的消耗，我是利用从下往上的方式，这样免去了边界的处理，坐标和方程中略微不同，利用是从0开始的坐标，程序源代码如下所示：

/*
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
*/
#include<stdio.h>
int a[15][15],i,j;
int main()
{
for (i=0;i<15;i++)
for (j=0;j<=i;j++)
scanf("%d",&a[i][j]);
for (i=13;i>=0;i--)
for (j=0;j<=i;j++)
a[i][j]+=a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
printf("%d\n",a[0][0]);
return 0;
}