8.8. Задача «Расставить скобки»

В этом параграфе вы научитесь находить оптимальный способ расставить скобки в арифметическом выражении, чтобы получить наибольшее значение. Задача учит динамическому программированию с двумя таблицами — для минимальных и максимальных значений подвыражений. Вы увидите, как даже простое выражение требует аккуратного перебора всех вариантов и рекурсивного деления на подзадачи.

Ключевые вопросы параграфа

• Почему результат арифметического выражения зависит от порядка скобок?

• Как использовать динамическое программирование для перебора всех вариантов группировки?

• Как устроены таблицы для хранения минимальных и максимальных значений подвыражений?

Упражнение

Для выражения существуют два способа расставить скобки: и .

Условие упражнения

Для максимального значения нужно поставить в скобки выражение .

• Входные данные: Ввод содержит только строку длиной для некого с символами . Каждый символ на чётной позиции — это цифра (то есть целое число от 0 до 9), а на нечетной позиции — одна из трёх операций из .
• Выходные данные: Максимальное значение данного арифметического выражения из всех возможных порядков арифметических операций.
• Ограничения: — таким образом, строка содержит максимум символов.

Пример 1

Решение

Рассмотрим решение задачи. Каждая из пяти операций в выражении

может быть последней — внешней. Рассмотрим случай, в котором последняя операция — «», то есть умножение. В этой ситуации нам необходимо поместить два подвыражения в скобки

таким образом, чтобы произведение значений было максимальным. Чтобы это выяснить, мы находим минимальные и максимальные значения данных двух подвыражений:

На основании этих значений мы заключаем, что общее значение произведения составляет .

Предположим, что вводный набор данных имеет форму

где каждая — это цифра, а каждая — базовая арифметическая операция. Сказанное выше предполагает, что мы вычисляем минимальное и максимальное значение каждого подвыражения в форме

где . Пусть и — минимальное и максимальное значение соответственно. Тогда

Базовый случай — это :

Эти два рекуррентных соотношения позволяют нам вычислить оптимальные значения , изучив все возможные варианты разделения на два подвыражения и .

Тогда наше рекуррентное соотношение говорит о том, что дерево состоит из корня и двух поддеревьев. Для нахождения оптимальной формы дерева мы анализируем все возможные корни (за это отвечает параметр ), а затем составляем дерево из двух оптимальных поддеревьев.

Как сделать из рекуррентного соотношения рекурсивный алгоритм

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

Перед тем, как начать вычисления, проверяется, не сохранены ли уже эти значения в , где — это ассоциативный массив, хранящий уже вычисленные результаты.

Если запись отсутствует, рекурсивная процедура вычисляет два значения, используя рекуррентное соотношение, сохраняет их в таблицу и выдаёт их. Конечный ответ соответствует и .

Время выполнения составляет : есть возможных пар , для каждой из которых рекурсивная процедура проверяет возможные значения для .

Для переведения рекурсивного алгоритма в итерационный используются двумерные таблицы и , в которых хранятся минимальные и максимальные значения всех подвыражений. Заполняя данные таблицы, нам нужно убедиться, что к окончанию вычислений оптимальных значений для оптимальные значения и для всех уже вычислены.

Один из способов сделать это — перечислить все пары в порядке возрастания значения . Чтобы это сделать, в псевдокоде ниже используется параметр .

1MaxValue(d[0],op[0],d[1],op[1],…d[n]):
2    mins, maxs = 2d-arrays of size (n+1)×(n+1)
3    fill mins with +infinity, fill maxs with -infinity
4    for i from 0 to n:
5        mins[i][i]=d[i], maxs[i][i]←d[i]​
6    for s from 1 to n:
7        for l from 1 to n-s:
8            r = l+s
9            for m from l to r-1:
10                a = mins[l][m] op[m] mins[m+1][r]
11                b = mins[l][m] op[m] maxs[m+1][r]
12                c = maxs[l][m] op[m] mins[m+1][r]
13                d = maxs[l][m] op[m] maxs[m+1][r]
14                mins[l][r] = min(mins[l][r],a,b,c,d)
15                maxs[l][r] = max(maxs[l][r],a,b,c,d)
16    return maxs[0][n]

Что дальше

Теперь вы умеете вычислять максимальное значение арифметического выражения, расставляя скобки в нужном порядке. Вы научились использовать динамическое программирование с запоминанием минимальных и максимальных значений и применять аккуратные рекурсивные формулы.

Далее — финальный параграф главы. В нём мы кратко обобщим ключевые идеи, которые вы встретили, и покажем, как они складываются в систему.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Порядок выполнения операций влияет на результат арифметического выражения — важно правильно расставить скобки.
• Можно эффективно найти максимальное значение, если сохранять минимумы и максимумы всех подвыражений в таблицах.
• Динамическое программирование позволяет избежать повторных вычислений и уменьшает время работы с экспоненциального до кубического.
• Даже при небольшом числе операций количество возможных расстановок скобок велико — поэтому важно автоматизировать перебор.