-3

我正在尝试解决项目欧拉问题18/67。我有一个尝试，但它不正确。

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)

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

4

2 回答 2

1

你的算法是错误的。考虑一下底行是否有像 1000000 这样的大数字。您的算法可能会遵循一条根本找不到它的路径。

这个问题暗示这个问题可以是蛮力的，但也有一种更聪明的方法来解决它。

不知何故，您的算法将需要考虑所有可能的路径/总和。

蛮力法是从上到下逐一尝试。

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

于 2013-05-14T22:37:43.750 回答
0

这是算法。我会让你想办法给它编码。

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

还有一种自上而下的算法与上面给出的算法是对偶的。我也会让你弄清楚的。

于 2013-05-15T03:08:08.083 回答