最大路径三角形 [英] Max path triangle

问题描述

我有一个三角形，它有两百行，我必须找到从三角形的顶部到底部的最大距离.

I have a triangle with two-hundred rows, where I have to find the maximum distance to get from the top to the bottom of the triangle.

   5
  9 8
 5 4 6
9 7 3 4

此处，最短距离为5 + 8 + 4 + 3 = 20.最大距离为5 + 9 + 5 + 9 = 28.

Here, the shortest distance would be 5+8+4+3=20. The maximum distance would be 5+9+5+9=28.

我对要实现的算法有很好的了解，但我正在努力将其转换为代码.

I have a good idea of the algorithm I want to implement but I am struggling to turn it into code.

我的计划是:从第二行到最后一行，从最下面的行开始添加最大可能路径，然后迭代到最上面.

My plan is: start at the 2nd to last row, add the maximum of the possible paths from the bottom row, and iterate to the top.

例如，上面的三角形将变成:

For instance, the above triangle would turn into:

   28
  23 19
 14 11 10
9 7 3 4

这比暴力破解要有效得多，但是我有两个普遍的问题:

This is vastly more efficient than brute-forcing, but I have two general questions:

1. 使用蛮力，如何列出从上到下的所有可能路径 底部(只能移动到相邻点)?我尝试使用这个 (三角形是包含三角形的列表的列表):

1. Using brute-force, how do I list all the possible paths from top to bottom (can only move to adjacent points)? I tried using this (triangle is the list of lists containing the triangle):

points=list(itertools.product(*triangle))  

但这包含每一行的所有可能组合，而不仅仅是 相邻成员. 欧拉计划#18-如何使用Python暴力破解树状结构中的所有可能路径? 这在某种程度上解释了一种可能的方法，但我想使用 itertools和任何其他模块(尽可能使用pythonic)

but this contains all possible combinations from each row, not just adjacent members. Project Euler #18 - how to brute force all possible paths in tree-like structure using Python? This somewhat explains a possible approach, but I'd like to use itertools and any other modules (as pythonic as possible)

我将如何迭代添加每个最大值的策略 从上一行并迭代到顶部?我知道我必须 实现嵌套循环:

How would I go about iterating the strategy of adding each maximum from the previous row and iterating to the top? I know I have to implement a nested loop:

for x in triangle:
    for i in x:
        i+=? #<-Not sure if this would even increment it

edit:
what I was thinking was:
triangle[y][x] = max([triangle[y+1][x],triangle[y+1][x+1]])

推荐答案

它不使用itertools，它是递归的，但是我记住了结果，所以它仍然很快...

It does not use itertools, it is recursive, but I memoize the results, so its still fast...

def memoize(function):
    memo = {}
    def wrapper(*args):
      if args in memo:
        return memo[args]
      else:
        rv = function(*args)
        memo[args] = rv
        return rv
    return wrapper



@memoize
def getmaxofsub(x, y):
    if y  == len(triangle) or x>y: return 0
    #print x, y
    return triangle[y][x] + max(getmaxofsub(x, y+1), getmaxofsub(x+1, y+1))


getmaxofsub(0,0)

我再读几次您的算法建议，并且您的累积三角形"存储在记忆修饰符的memo中，因此最终它非常相似.如果要防止在通过三角形进行递归向下调用"期间存在大量堆栈，则可以通过调用getmaxofsub() bottom-> up来填充备忘录的缓存.

I read your algorithm suggestion some more times and your "cumulative triangle" is stored in memoof the memoized decorator, so in the end it is very similar. if you want to prevent that there is big stack during recursive "down calling" through the triangle, you can fill the cache of memoize by calling getmaxofsub() bottom -> up.

for i in reversed(range(len(triangle))):
    getmaxofsub(0, i), getmaxofsub(i//2, i), getmaxofsub(i, i)

print getmaxofsub(0,0)

修改

getmaxofsub:此功能如何工作?首先，您必须知道，不能将三角形划分为子三角形.我以您的三角形为例:

getmaxofsub: How does this function work? First you have to know, that you can't divide your triangle in sub triangles. I take your triangle as an example:

   5
  9 8
 5 4 6
9 7 3 4

那是完整的.峰的坐标"是x = 0，y = 0.

That's the complete one. The "coordinates" of the peak are x=0, y=0.

现在，我提取峰x = 0，y = 1的子三角形:

Now I extract the sub triangle of the peak x=0, y=1:

  9
 5 4
9 7 3

或x = 1，y = 2

or x=1, y=2

 4
7 3

这就是我的算法的工作方式:整个三角形(x = 0，y = 0)的峰问其子三角形(x = 0，y = 1)和(x = 1，y = 1)， 您到地面的最大距离是多少?"他们每个人都会问自己的子三角形，依此类推... 这将一直进行到函数到达地面/y==len(triangle)为止:地面条目要询问其子三角形，但由于它们都不是，因此得到答案0. 在每个三角形调用其子三​​角形之后，它会决定哪个更大，再加上自己的值并返回该和.

So this is how my algorithm works: The peak of the whole triangle (x=0, y=0) asks its sub triangles (x=0, y=1) and (x=1, y=1), "What is your maximum distance to the ground?" And each of them will ask their sub-triangles and so on… this will go on until the function reaches the ground/y==len(triangle): The ground-entries want to ask their sub triangles, but since their is none of those, they get the answer 0. After each triangle has called their sub triangles, it decides, which one is the greater one, add their own value and return this sum.

所以现在您看到了，该算法的原理是什么.这些算法称为递归算法.您会看到，调用自身的函数是非常标准的……并且可以正常工作……

So now you see, what is the principle of this algorithm. Those algorithms are called recursive algorithms. You see, a function calling itself is pretty standard… and it works…

因此，如果您考虑整个算法，您会看到很多次三角形被多次调用，它们会询问它们的次三角形，依此类推……但是每次它们返回相同的值.这就是为什么我使用memorize -decorator的原因:如果使用相同的参数x和y调用函数，则装饰器将返回这些参数的最后一个计算值，并避免耗时的计算……这是一个简单的缓存...

So, if you think about this whole algorithm, you would see that a lot of sub-triangles are called several times and they would ask their sub-triangles and so on… But each time they return the same value. That is why I used the memorize-decorator: If a function is called with the same arguments x and y, the decorator returns the last calculated value for those arguments and prevents the time-consuming calculation… It is a simple cache…

这就是为什么此函数像递归算法一样容易实现并且像迭代一样快...

That is why this function is as easy to implement as a recursive algorithm and as fast as a iteration...

这篇关于最大路径三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！