Задача
Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 23.
То есть, 3 + 7 + 4 + 9 = 23.
Найдите максимальную сумму пути от вершины до основания следующего треугольника:
Примечание: Так как в данном треугольнике всего 16384 возможных маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов. Однако похожая Задача 67 с треугольником, состоящим из сотни строк, не решается перебором (brute force) и требует более умного подхода!
Решение
Я делаю его сразу для Задачи 67. Там треугольник большой и читается из файла. Здесь треугольник небольшой и его можно сразу поместить в программу. Разница только в этом, а алгоритм будет тот же самый.
Начнём с размещения треугольника в памяти:
В нём 15 строк, а всего чисел 120 (старая добрая сумма (15 * 15 + 15) / 2), что я определил как константы N и SIZE.
Это одномерный массив. Чтобы установить связность элементов друг с другом, нужно разбить его на строки. У каждой строки есть смещение и длина. Очевидно, у первой строки смещение 0 и длина 1, у второй смещение 1 и длина 2, у третьей смещение 3 и длина 3, и т.д. Легко видеть, что длина строки равна порядковому номеру строки, а смещение это смещение предыдущей строки плюс её длина.
Из каждого элемента строки можно перейти в один из двух элементов в следующей строке. Если текущий элемент имеет индекс i, то перейти можно в элемент i или i+1 в следующей строке.
Поиск пути
Главная проблема, которая ведёт к полному перебору, это отсутствие определённости. От вершины треугольника доступны два элемента – 95, 64. Какой выбрать для следующего шага? Если выбрать 95, то у него далее будут доступны два элемента: 17, 47. Но эти два элемента меньше, чем у его конкурента 64, отброшенного ранее – 47, 82. То есть само значение элемента ни о чём не говорит, нужно учитывать только всю сумму. Что и приводит к полному перебору путей.
Поэтому нужно начинать с ситуации определённости. А когда она есть? Когда мы пришли к развилке из двух последних элементов. Так как дальше ничего нет, то однозначно можно выбрать больший из них.
А раз последний элемент определён, то и предпоследний, который в него ведёт, становится определённым. Прибавим к предпоследнему элементу последний, и теперь предпоследний содержит финальную сумму себя и последнего элемента. Можно подняться на строку выше и повторить.
Нижние элементы передают свой "вес" верхним, верхние передают общий с нижними "вес" ещё выше и т.д.
Вообще можно складывать прямо в треугольнике, но тогда потеряются оригинальные значения элементов. Для этой задачи они, впрочем, не нужны. Я всё же храню веса в отдельном массиве weights, такого же размера и с такой же структурой, как и треугольник.
Далее делаю вывод значений треугольника и соответствующих им весов:
Это необязательная часть, просто для иллюстрации. Самое же интересное, что максимальную сумму пути искать уже не надо. Так как все веса, начиная от низа, сложились, и всякий раз для передачи наверх выбирался больший из них, то финальная сумма уже вычислена и лежит в вершине треугольника:
Ссылка на онлайн-компилятор языка C с текстом программы
При желании можно восстановить весь маршрут от вершины. Для этого из веса вершины вычитаем её собственное значение, а остаток ищем среди двух смежных элементов. Переходим на тот, чей вес совпадает с остатком, и повторяем процедуру.
Вся подборка задач: