В этом выпуске рассмотрим классическую задачу, известную под названием «Золотая гора». На CheckiO её реализовали в этой задаче.
Представьте себе треугольник, составленный из чисел. Одно число расположено в вершине. Ниже размещено два числа, затем три, и так до нижней грани. Вы начинаете на вершине, и нужно спуститься к основанию треугольника. За каждый ход вы можете спуститься на один уровень и выбрать между двумя числами под текущей позицией. По ходу движения вы «собираете» и суммируете числа, которые проходите. Ваша цель – найти максимальную сумму, которую можно получить из различных маршрутов.
Рассмотрим различные методы решения.
Рекурсия
Первым делом в голову приходит мысль использовать рекурсию и просчитать все пути от вершины. Когда мы спускаемся на один уровень, то все доступные числа ниже образуют новый меньший треугольник, и можно запустить нашу функцию уже для нового подмножества и так пока не достигнем основания.
def golden_pyramid(triangle, row=0, column=0, total=0):
global count
count += 1
if row == len(triangle) - 1:
return total + triangle[row][column]
return max(golden_pyramid(triangle, row + 1, column, total + triangle[row][column]),
golden_pyramid(triangle, row + 1, column + 1, total + triangle[row][column]))
Как мы видим, на первом уровне мы запустим нашу функцию два раза, затем 4, 8, 16 раз и так далее. В итоге мы получим сложность алгоритма 2N и, например, для 100-уровневой пирамиды нам нужно будет уже где-то ≈1030 вызовов функции. Многовато.
Динамическое программирование
Что если попробовать использовать принцип динамического программирования и разбить нашу проблему на множество мелких подзадач, результаты которых мы затем аккумулируем. Попробуйте взглянуть на треугольник вверх ногами. А теперь на второй уровень (то есть предпоследний от основания). Для каждой ячейки мы можем решить, каким будет лучший выбор в наших маленьких трёхэлементных треугольничках. Выбираем лучший, суммируем с рассматриваемой ячейкой и записываем результат. Таким образом, мы получили наш треугольник, но на один уровень ниже. Повторяем данную операцию снова и снова. В результате нам нужно (N-1)+(N-2)+…2+1 операций и сложность алгоритма равна N2.
def golden_pyramid_d(triangle):
tr = [row[:] for row in triangle] # copy
for i in range(len(tr) - 2, -1, -1):
for j in range(i + 1):
tr[i][j] += max(tr[i + 1][j], tr[i + 1][j + 1])
return tr[0][0]
Решения игроков CheckiO
Пользователь gyahun_dash написал интересную реализацию описанного выше метода ДП в своем решении «DP». Он использовал reduce, чтобы проходить по парам строк, и map чтобы обработать каждую из них.
from functools import reduce
def sum_triangle(top, left, right):
return top + max(left, right)
def integrate(lowerline, upperline):
return list(map(sum_triangle, upperline, lowerline, lowerline[1:]))
def count_gold(pyramid):
return reduce(integrate, reversed(pyramid)).pop()
Игрок evoynov использовал двоичные числа, чтобы перебрать все возможные маршруты, представленные как последовательность 1 и 0 в своем решении «Binaries». И это наглядный пример сложности алгоритма с рекурсией и перебором всех маршрутов.
def count_gold(p):
path = 1 << len(p) res = 0 while bin(path).count("1") != len(p) + 1: s = ind = 0 for row in range(len(p)): ind += 1 if row > 0 and bin(path)[3:][row] == "1" else 0
s += p[row][ind]
res = max(res, s)
path += 1
return res
И чтобы не было скучно, посмотрим на легкий мозгодробитель от пользователя nickie и его однострочник «Functional DP», который только формально состоит из двух строк. Конечно, это решение из категории «Творческих» («Creative»). Не думаю, что автор использует такое на боевом коде. А просто для так для веселья, почему бы и нет.
ount_gold=lambda p:__import__("functools").reduce(lambda D,r:[x+max(D[j],D[j+1])
for j,x in enumerate(r)],p[-2::-1],list(p[-1]))[0]
Вот и всё на сегодня. Делитесь вашими идеями и мыслями.
Спасибо CheckiO за интересную задачу.
Ещё интересное для вас:
— Тест «Насколько хорошо вы разбираетесь в C#?»
— Блиц-тест «Настоящий ли ты фронтендер?»
— Меньше готовить, больше кодить: обзор питания с доставкой на дом.
