Для выражения $(3+2\times 4)$ существуют два способа расставить скобки: $(3+(2\times4))=11$ и $((3+2) \times 4)=20$.
✒️ Упражнение:
Для максимального значения нужно поставить в скобки выражение $(5-8+7\times4-8+9)$.
- Входные данные: Ввод содержит только строку $s$ длиной $2n+1$ для некого $n$ с символами $s_0,s_1, \dotsc, s_{2n}$. Каждый символ на чётной позиции $s$ — это цифра (то есть целое число от 0 до 9), а на нечетной позиции — одна из трёх операций из ${\tt {+,-,*}}$.
- Выходные данные: Максимальное значение данного арифметического выражения из всех возможных порядков арифметических операций.
- Ограничения: $0 \le n \le 14$ — таким образом, строка содержит максимум $29$ символов.
Пример 1
Ввод | Вывод |
---|---|
5-8+7*4-8+9 | 200 |
- $200=(5-((8+7)\times(4-(8+9))))$
Рассмотрим решение задачи. Каждая из пяти операций в выражении $$ (5-8+7\times4-8+9) $$
может быть последней — внешней. Рассмотрим случай, в котором последняя операция — «$\times$», то есть умножение. В этой ситуации нам необходимо поместить два подвыражения в скобки $$ (5-8+7) \text{ и } (4-8+9), $$
таким образом, чтобы произведение значений было максимальным. Чтобы это выяснить, мы находим минимальные и максимальные значения данных двух подвыражений:
На основании этих значений мы заключаем, что общее значение произведения составляет $130$.
Предположим, что вводный набор данных имеет форму
где каждая $d_i$ — это цифра, а каждая $op_j \in {+,-,\times}$ — базовая арифметическая операция. Сказанное выше предполагает, что мы вычисляем минимальное и максимальное значение каждого подвыражения в форме
где $0 \le l \le r \le n$. Пусть $minValue(l,r)$ и $maxValue(l,r)$ — минимальное и максимальное значение $E_{l,r}$ соответственно. Тогда
Базовый случай — это $l=r$: $$ minValue(l,l)=maxValue(l,l)=d_l . $$
Эти два рекуррентных соотношения позволяют нам вычислить оптимальные значения $E_{l,r}$, изучив все возможные варианты разделения $E_{l,r}$ на два подвыражения $E_{l,m}$ и $E_{m+1,r}$.
Тогда наше рекуррентное соотношение говорит о том, что дерево состоит из корня и двух поддеревьев. Для нахождения оптимальной формы дерева мы анализируем все возможные корни (за это отвечает параметр $m$), а затем составляем дерево из двух оптимальных поддеревьев.
Как обычно, сделать из рекуррентного соотношения рекурсивный алгоритм довольно просто. Рекурсивная процедура берёт индексы $l$ и $r$ в качестве параметров и использует их для вычисления минимального и максимального значения подвыражения $E_{l,r}$. Перед тем, как начать вычисления, проверяется, не сохранены ли уже эти значения в $table[l,r]$, где $table$ — это ассоциативный массив, хранящий уже вычисленные результаты. Если запись $table[l,r]$ отсутствует, рекурсивная процедура вычисляет два значения, используя рекуррентное соотношение, сохраняет их в таблицу и выдаёт их. Конечный ответ соответствует $l=0$ и $r=n$. Время выполнения составляет $O(n^3)$: есть $O(n^2)$ возможных пар $(l,r)$, для каждой из которых рекурсивная процедура проверяет возможные значения для $l \le m < r$.
Для переведения рекурсивного алгоритма в итерационный используются двумерные таблицы $mins[0..n][0..n]$ и $maxs[0..n][0..n]$, в которых хранятся минимальные и максимальные значения всех подвыражений. Заполняя данные таблицы, нам нужно убедиться, что к окончанию вычислений оптимальных значений для $E_{l,r}$ оптимальные значения $E_{l,m}$ и $E_{m+1,r}$ для всех $m$ уже вычислены. Один из способов сделать это — перечислить все пары $(l,r)$ в порядке возрастания значения $r-l$. Чтобы это сделать, в псевдокоде ниже используется параметр $s=r-l$.
MaxValue(d[0],op[0],d[1],op[1],…d[n]):
mins, maxs = 2d-arrays of size (n+1)×(n+1)
fill mins with +infinity, fill maxs with -infinity
for i from 0 to n:
mins[i][i]=d[i], maxs[i][i]←d[i]
for s from 1 to n:
for l from 1 to n-s:
r = l+s
for m from l to r-1:
a = mins[l][m] op[m] mins[m+1][r]
b = mins[l][m] op[m] maxs[m+1][r]
c = maxs[l][m] op[m] mins[m+1][r]
d = maxs[l][m] op[m] maxs[m+1][r]
mins[l][r] = min(mins[l][r],a,b,c,d)
maxs[l][r] = max(maxs[l][r],a,b,c,d)
return maxs[0][n]