我们可以使用回溯来解决这个问题。要对任何给定行中三角形的每个元素执行此操作,我们必须确定当前元素和下一行中三个连接的相邻元素之和的最大值,或者
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
对于位置 (row,col) 中的元素,将[next[col-1],next[col],next[col+1]]
提供row = next 中的连接邻居,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 in row])
写成
triangle[row][i] = max([elem + next[n] for n in neigh(i,len(next))])
如果我们逐行迭代三角形并且 curr 是任何给定的行,那么 i 是该行的第 i 个 col 索引,那么我们可以写
curr[i]=max(next[n]+e for n in neigh(i,len(next)))
现在我们必须迭代读取当前行和下一行的三角形。这可以作为
for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):
然后我们使用 enumerate 生成一个索引元组和元素本身
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 reference
route = triangle[:] #This will also not work, because triangle is a list of list
#and individual list would be copied with reference
所以我们必须使用deepcopy
模块
import copy
route = copy.deepcopy(triangle) #This will work
并将 traverse 重写为
>>> 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)))
我们最终得到另一个三角形,其中每个元素都给出了可能的最高路线成本。要获得实际路线,我们必须使用原始三角形并向后计算
所以对于 index 处的元素[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,但不同之处在于表示。Euler 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])
>>>