路徑具有最大總和爲三角形

實施例的所有可能的路徑中的最大總和：

 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

路徑具有最大總和爲三角形

回答

相關問題