python - 在金字塔/三角形中查找相邻数字的最大和时输出错误

Question

我解决Problem 18 on Project Euler并为它编写了如下代码:

v = '''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'''.strip().split('\n')


last_ind = 0
max_sum = 75
for row in v[1:]:
    row = row.split(' ')
    num1 = int(row[last_ind])
    num2 = int(row[last_ind+1])
    if num1 > num2:
        max_sum+=num1
    else:
        max_sum+=num2
        last_ind = last_ind+1
        
print(max_sum)    

我得到了答案 1064 但它写的是 1074到处。有人可以建议我我可能做错了什么。通过手动计算每一行，我得到 1064 .这里有什么问题？

Answer 1

您假设最佳路径将始终通过具有最大值(value)的子项向下移动，但事实并非如此。具有较小值的子级可能会(在较低层)找到一个更大的值，这不仅仅是对临时不太理想的值的补偿。
因此，您的算法在第一次迭代中将从第二行的 75 变为 95。但事实证明这是错误的选择。你必须想出一个更好的算法。您会在有关此特定挑战的其他问答中找到灵感，例如 this one .
在这里您可以看到最佳路径:


小路


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