Лиза (задача)

Подростки очень нуждаются в карманных деньгах, и Лиза — не исключение. Карманных денег, выданных в прошлом месяце, ей хватило только на неделю. В связи с этим она решилась поговорить с отцом. Ее отец — математик — поступил весьма оригинальным образом: он написал на листке бумаги выражение, содержащее числа, знаки сложения и умножения, и предложил Лизе расставить в этом выражении скобки. Полученный результат и будет той суммой, которую Лиза получит на карманные расходы. В интересах Лизы расставить скобки таким образом, чтобы результат был максимальным.
Ваша задача — помочь Лизе, расставив скобки таким образом, чтобы результат был макси-мально возможным. А отцу Лизы интересно, какой минимальной суммой он мог «отделаться».

Решение:
Так как здесь возможные знаки операций – только сложение и умножение, то результат будет неотрицательным. Используем принцип динамического программирования ^[1].
Сначала опишем рекурсивное решение: вычислим результат выражения, разбив его на два под-выражения всеми возможными способами и выбрав из них наилучшее значение.
Для верхнего уровня это выглядит так:

Соответственно, каждое из получившихся подвыражений меньшей длины разбиваем таким же образом и находим его наилучшее значение.
Решение правильное, но неэффективное – в различных разбиениях некоторые подвыражения повторяются, и каждый раз их рекурсивное вычисление будет выполняться заново:

Чтобы избежать одних и тех же вычислений, добавим кэширование – будем сохранять значения каждого подвыражения и при повторном его использовании брать уже посчитанный результат.
Второй способ реализации этого алгоритма – без рекурсии, «снизу вверх»: вместо разбиения выражения сначала посчитаем значения подвыражений, состоящих из одной операции, затем на основе полученных результатов – для двух операций, и так далее.
Промежуточные результаты будем хранить в виде матрицы a[i][j] – минимум и максимум подвыражения, начинающегося с i–й операции длиной j операций. Тогда ответ для всего выражения будет находиться в a[1][n], где n – количество операций.

Автор: ymushnikova

Источник ^[2]