Представьте, что у вас есть пирамида, построенная из чисел, как здесь:
Максимальная сумма последовательных чисел от верха до низа пирамиды равна 3 + 7 + 4 + 9 = 23. Ваша задача — разработать алгоритм, который находит максимальную сумму пути внутри пирамиды.
Важно: забудьте о грубой силе. Это не является целью данного упражнения.
Вот тест, который вам нужно пройти:
longest_slide_down([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) #23
Как решить эту задачу без грубой силы?
Можно подумать, что лучшей отправной точкой для решения этой задачи будет верхушка пирамиды. Оттуда мы найдем все возможные пути сверху вниз с соответствующими суммами. При каждой сумме останется наибольшая.
Ну, этот подход будет использовать рекурсию. Если пирамида очень длинная, будет много путей, которые могут привести в никуда. Следовательно, делая этот подход не оптимальным. Давайте рассмотрим другой подход.
Вместо того, чтобы идти сверху вниз, мы могли бы начать снизу. Мы сохраним только те пути, которые в самом низу указывают, что имеют большую сумму, чем их аналоги. Давайте посмотрим на это более четко:
Продолжим реализацию кода.
Решения
Мы будем следовать трем различным подходам к решению этой задачи. Первое решение будет интенсивно использовать память. Второй будет повторно использовать массивы, переданные в качестве аргументов, что более эффективно, чем первое решение. Наконец, мы увидим, как можно легко решить проблему с помощью метода reduce. Давайте начнем.
Первый подход
Мы начнем с массива перед последним и оттуда вычислим сумму вверх, сохраняя пути наибольшей суммы между массивами.
Второй подход
Чтобы полностью понять этот подход, давайте посмотрим, как работает .pop():
Имея это в виду, давайте перейдем к решению 2-го подхода:
Третий подход
Давайте немного рассмотрим функцию reduce(function, iterable), прежде чем переходить к решениям. Этот подход может быть самым элегантным, если мы правильно поймем концепции. Посмотрим:
Объяснив основы, давайте приступим к самому элегантному решению этой задачи кодирования:
