路径具有最大总和为三角形

实施例的所有可能的路径中的最大总和：

 1 
     2 1 
    1 2 3

然后所有可能路径之中的最大值为1+ 2 + 3 = 6

我的代码：

def maxSum(tri, n): 
    if n > 1: 
     tri[1][1] = tri[1][1]+tri[0][0] 
     tri[1][0] = tri[1][0]+tri[0][0] 
    for i in range(2, n): 
     tri[i][0] = tri[i][0] + tri[i-1][0] 
     tri[i][i] = tri[i][i] + tri[i-1][i-1] 
    for j in range(1, i): 
     if tri[i][j]+tri[i-1][j-1] >= tri[i][j]+tri[i-1][j]: 
      tri[i][j] = tri[i][j] + tri[i-1][j-1] 
     else: 
      tri[i][j] = tri[i][j]+tri[i-1][j] 
print max(tri[n-1]) 


#my list containing the triangle 
tri = [[1], [2,1], [1,2,3]] 
maxSum(tri, 3)

但我的代码打印输出5.Anyone请帮助我纠正我的代码？

来源

2017-10-29 Varun Shaandhesh

请准确定义“路径”是什么 –

您没有告诉我们什么定义了可能的路径。 –

@Varun Shaandhesh：如果它解决了你的问题，请按照https://stackoverflow.com/help/someone-answers更新线程 –

如果我没看错，这里就是你的要求

对于3的三角形，你将有6个元素，你想获得最大的路径（手段选择所有可能的3个要素组合，并取得3个组合号码，你将给予最大总和。这可以用一个简单的代码来实现

代码

`# declaring list 
tri=[[1], [2, 1], [1, 2, 3]]` 

#getting all possible 3 elements combinations out of available 6 elements. The below two lines will give list of tuples 
import itertools 
temptri=list(itertools.product(*tri)) 

#Converting tuple to list 
ftri=[] 
for i in temptri: 
    ftri.append(list(i)) 
#getting max sum of the avilable 3 elements combinations 
print sum(max(ftri, key=sum))

实施例的输入/输出

input 
tri=[[1], [2, 5], [1, 2, 3]] 
output 
6 

input 
[[1], [2, 5], [1, 2, 3]] 
output 
9 

input 
[[1], [2, 5], [1, 2, 3],[1,2,3,7]] 
output 
16

来源

2017-10-29 07:27:27

您还没有指定什么有效的路径，因此就像桑迪普拉德，我也做了一个假设：为了获得最大的数字的总和在三角形：

def maximum(x): 
    return max(x) 

triangle= [[1], [2, 1], [1, 2, 3],[2,3,4,5]] 
#the above can be represented as: 
#  1 
#  2 1 
#  1 2 3 
# 2 3 4 5 

max_numbers = list(map(maximum,triangle)) 
print(max_numbers,'====>',sum(max_numbers))

为您提供了最大数量的三角形和和其可扩展三角形的任何尺寸的

可以使代码甚至使用lambda功能更简洁：

print(sum(list(map(lambda x:max(x),triangle))))

来源

2017-10-29 08:22:38 Adarsh

路径具有最大总和为三角形

回答

相关问题