1 3和5的倍数
2 偶数斐波纳契数
3 最大的素数因子
4 最大的回文乘积
5 最小乘积
6 和平方差
7 第10001个素数
8 连串数字的最大乘积
9 特殊的毕达哥拉斯三元组
10 素数的和
11 在格子中最大的乘积
12 高度可约的三角形数
13 大整数求和
14 最长的考拉兹数
15 格子路径
16 幂方的数字和
17 数字字母统计
18 路径的最大和(1)
19 计算星期天的天数
20 阶乘数字和

路径的最大和(1)

问题 18

原题链接 http://projecteuler.net/problem=18

从下面的三角形顶部开始移动到下面一层相邻的数字,一直到底部,这条路径上的和为23.

3
7 4
4 6
8 5 9 3

也就是,3 + 7 + 4 + 9 = 23.

在下面的三角形中,找到从顶部到底部的路径的最大值

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中,也是同样的问题,但是有100层,你不可能使用暴力方法,所以需要更聪明的方法!

 

留言