Как изменить эти функции, чтобы они рекурсивно находили решение

Question

Это вопрос о задаче Эйлера № 67. (Найдите максимальный путь по треугольнику) Я знаю, что может быть плохим вкусом обратиться за помощью к ним.

У меня есть эти функции:

def chooseBest(rowOfTriangle):
    if len(rowOfTriangle) == 1:
        return rowOfTriangle
    return list(max(element) for element in zip(rowOfTriangle[0:-1],rowOfTriangle[1:]))

и

def consolidatePath(rowOfTriangle , bestPath):
    return list(sum(element) for element in zip(rowOfTriangle,bestPath))

, которые работают с набором данных, отформатированным следующим образом:

triangle = [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]]

где решение для этого треугольника будет выглядеть так:

consolidatePath(triangle[0],chooseBest(consolidatePath(triangle[1],chooseBest(consolidatePath(triangle[2],chooseBest(triangle[3]))))))

Это выводит (правильно):

[20]

Запись каждого вызова вложенной функции далека от оптимальной и станет невозможной, когда я увеличу масштаб до сотни строк задачи. Как я могу изменить consolidatePath и chooseBest, чтобы вызывать друг друга в случае необходимости?

EDIT: Разобрался.

Answer 1

Как то так?

def max_path(triangle, idx=0, total=0):
    if triangle:
        row = triangle[0]
        next = max(row[idx:idx+2])
        return max_path(triangle[1:], row.index(next), total+next)
    return total