编程挑战帮助（python）？

Question

我试图解决欧拉项目问题18/67。我有an attempt，但它不对。在

tri = '''\
    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'''
sum = 0
spot_index = 0

triarr = list(filter(lambda e: len(e) > 0, [[int(nm) for nm in ln.split()] for ln in tri.split('\n')]))
for i in triarr:
    if len(i) == 1:
        sum += i[0]
    elif len(i) == 2:
        spot_index = i.index(max(i))
        sum += i[spot_index]
    else:
        spot_index = i.index(max(i[spot_index],i[spot_index+1]))
        sum += i[spot_index]

print(sum)

当我运行程序时，它总是有点偏离正确的和/输出值。我很确定这是一个算法问题，但我不知道该如何解决，也不知道解决原始问题的最佳方法是什么。在

Answer 1

这是算法。我会让你想出一个编码的方法。在

从最下面的两行开始。在next to bottom行的每个元素上，通过将与next to bottom row的当前元素对应的底行的两个元素的最大值相加，计算出达到该元素时的总和。例如，给定上面的示例，倒数第二行的最左边的元素是63，如果您到达那个元素，您肯定会选择它右边的子元素62。所以可以用63+62=125替换下一行的63。对倒数第二行的每个元素执行相同的操作；将得到125、164、102、95、112、123、165、128、166、109、112、147、100、54。现在删除最下面的一行，在缩小的三角形上重复。在

还有一个自顶向下的算法，它与上面给出的算法是对偶的。我也会让你知道的。在

Answer 2

你的算法错了。考虑一下下面一行是否有一个像1000000这样的大数字。你的算法可能会走一条根本找不到的路径。在

这个问题暗示了这个问题可以被粗暴地强迫，但也有一个更聪明的方法来解决它。在

你需要考虑所有可能的算法。在

蛮力法是自上而下尝试每一个。在

聪明的方法是使用一种叫做动态编程的技术