在给定输入中找到最大路径

在给定输入中找到最大路径

我们可以使用回溯来解决此问题。为此，对于给定行中三角形的每个元素，我们必须确定当前元素与下一行中三个相邻邻居的和的最大值，或者

if elem = triangle[row][col] and the next row is triangle[row+1]then backtrack_elem = max([elem + i for i in connected_neighbors of col

in row])

首先尝试找到一种确定方法

connected_neighbors of col in row

在位置的ELEM（行，列），连接在相邻行=下一个将被

[next[col-1],next[col],next[col+1]]

提供`col - 1

=0

和

col+1 < len(next)`。这是示例实现

>>> def neigh(n,sz):    return [i for i in (n-1,n,n+1) if 0<=i<sz]

这将返回已连接邻居的索引。

现在我们可以写

backtrack_elem = max([elem + i for i in connected_neighbors of col inrow])

为

triangle[row][i] = max([elem + next[n] for n in neigh(i,len(next))])

如果我们按行迭代三角形，并且curr是给定的行，则i是该行的ith col索引，则可以编写

curr[i]=max(next[n]+e for n in neigh(i,len(next)))

现在我们必须迭代三角形以一起读取当前行和下一行。这可以做到

for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):

然后我们使用枚举生成索引元组和elem本身

for (i,e) in enumerate(curr):

然后聚在一起，我们有

>>> for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):    for (i,e) in enumerate(curr):        curr[i]=max(next[n]+e for n in neigh(i,len(next)))

但是上述 *** 作具有破坏性，我们必须创建原始三角形的副本并对其进行处理

route = triangle # This will not work, because in python copy is done by referenceroute = triangle[:] #This will also not work, because triangle is a list of list         #and individual list would be copied with reference

所以我们必须使用

deepcopy

模块

import copyroute = copy.deepcopy(triangle) #This will work

并重写为

>>> for (curr,next) in zip(route[-2::-1],route[::-1]):    for (i,e) in enumerate(curr):        curr[i]=max(next[n]+e for n in neigh(i,len(next)))

我们最终得到了另一个三角形，其中每个元素都给出了最高的路线成本。要获得实际路线，我们必须使用原始三角形并向后计算

因此，对于索引处的elem来说

[row,col]

，最高的路由成本是route [row]
[col]。如果遵循最大路由，则下一个元素应该是连接的邻居，并且路由开销应该是route [row] [col]-orig [row]
[col]。如果我们逐行迭代，我们可以写成

i=[x for x in neigh(next,i) if x == curr[i]-orig[i]][0]orig[i]

并且我们应该从峰值元素开始向下循环。因此，我们有

>>> for (curr,next,orig) in zip(route,route[1:],triangle):    print orig[i],    i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]

让我们举一个复杂的例子，因为您的例子太微不足道了，无法解决

>>> triangle=[          [3],          [7, 4],          [2, 4, 6],          [8, 5, 9, 3],          [15,10,2, 7, 8]         ]>>> route=copy.deepcopy(triangle) # Create a Copy

生成路线

>>> for (curr,next) in zip(route[-2::-1],route[::-1]):    for (i,e) in enumerate(curr):        curr[i]=max(next[n]+e for n in neigh(i,len(next)))>>> route[[37], [34, 31], [25, 27, 26], [23, 20, 19, 11], [15, 10, 2, 7, 8]]

最后我们计算出路线

>>> def enroute(triangle):    route=copy.deepcopy(triangle) # Create a Copy    # Generating the Route    for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row        for (i,e) in enumerate(curr): #Backtrack calculation curr[i]=max(next[n]+e for n in neigh(i,len(next)))    path=[] #Start with the peak elem    for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row        path.append(orig[i])        i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]    path.append(triangle[-1][i]) #Don't forget the last row which    return (route[0],path)

为了测试我们的三角形

>>> enroute(triangle)([37], [3, 7, 4, 8, 15])

---

通过阅读jamylak的评论，我意识到这个问题类似于Euler
18，但是区别在于表示形式。欧拉18中的问题考虑一个金字塔，因为该问题中的问题是直角三角形。当您可以阅读我对他的评论的答复时，我解释了结果不同的原因。但是，可以很容易地将此​​问题移植到与Euler
18一起使用的地方。这是端口

>>> def enroute(triangle,neigh=lambda n,sz:[i for i in (n-1,n,n+1) if 0<=i<sz]):    route=copy.deepcopy(triangle) # Create a Copy    # Generating the Route    for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row        for (i,e) in enumerate(curr): #Backtrack calculation curr[i]=max(next[n]+e for n in neigh(i,len(next)))    path=[] #Start with the peak elem    for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row        path.append(orig[i])        i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]    path.append(triangle[-1][i]) #Don't forget the last row which    return (route[0],path)>>> enroute(t1) # For Right angle triangle([1116], [75, 64, 82, 87, 82, 75, 77, 65, 41, 72, 71, 70, 91, 66, 98])>>> enroute(t1,neigh=lambda n,sz:[i for i in (n,n+1) if i<sz]) # For a Pyramid([1074], [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93])>>>