python - 项目欧拉问题 18 : finding the best route in a triangular grid

Question

Project Euler problem 18要求我们找到三角形网格中从上到下总和最大的路线。

我的程序应该能够接受如下所示的输入。测试用例的数量 (2) 出现在第一行，然后对于每个测试用例给出行数 (4)，然后是测试用例的数据，每行一行。

2 
4 
3 
7 4
2 4 6
8 5 9 3
6
690
650 901
65 774 67
435 248 677 385
878 90 378 191 703
141 296 143 756 938 529

程序应该为每个测试用例生成一行输出，给出具有最大总和的路线:

23 
4176

我尝试使用Python来实现它。

代码如下:

def triangle(rows):
    PrintingList = list()
    for rownum in range (rows ):     
        PrintingList.append([])
        newValues = raw_input().strip().split()
        PrintingList[rownum] += newValues
    return PrintingList

def routes(rows,current_row=0,start=0): 
        for i,num in enumerate(rows[current_row]): 
            if abs(i-start) > 1:   
                continue
            if current_row == len(rows) - 1: 
                yield [num]
            else:
                for child in routes(rows,current_row+1,i):
                    yield [num] + child

testcases = int(raw_input())
for num in range(testcases):
    rows= int(raw_input())
    triangleinput = triangle(rows)
    max_route = max(routes(triangleinput),key=sum)
    sum(max_route)

当我输入此内容时:

1
3
1
2 3
4 5 6

我收到此错误:

Traceback (most recent call last):
  File "Maximum Route.py", line 23, in <module>
    max_route = max(routes(triangleinput),key=sum)
TypeError: unsupported operand type(s) for +: 'int' and 'str'

需要一些指导..请指出是否还有其他错误...谢谢...

Answer 1

问题是这样的:

newValues = raw_input().strip().split()

您需要将输入转换为整数:

newValues = map(int, raw_input().split())