Задача о расстановке знаков в выражении — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники)
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Задача о расстановке знаков в выражении''' — задача о нахождении максимального значения выражения, полученного расстановкой знаков  <tex dpi = "120">+, \times</tex> и скобок в последовательности <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 0)</tex>.
+
{{ Задача
 +
|definition =
 +
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \ldots, a_n \ (a_i \geqslant 0)</tex>. Требуется расставить знаки <tex dpi = "120">+, \times</tex> и скобки в последовательности, чтобы значение полученного арифметического выражения было максимальным.
 +
}}
  
 
== Решение ==
 
== Решение ==
Данная задача решается с использованием принципа оптимальности на подотрезке[http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D0.BE.D0.B4.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.B0.D1.85]. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dots, a_j</tex>.
+
Данная задача решается с использованием [[Динамическое_программирование | принципа оптимальности на подотрезках]]. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \ldots, a_j</tex>.
 
Получаем следующие соотношения: <br />
 
Получаем следующие соотношения: <br />
 
* <tex>d[i][i] = a_i </tex><br />
 
* <tex>d[i][i] = a_i </tex><br />
* <tex>d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k] \times d[k+1][j])] \ (i < j)</tex> <br />
+
* <tex>d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k] \cdot d[k+1][j])] \ (i < j)</tex> <br />
 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.
 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.
 +
 
== Доказательство ==
 
== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции +и “*”, расставить скобки так, чтобы результат оказался максимальным.
+
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с i-го и заканчивая j-м. Запоминать результат оптимального решения соответствующей подзадачи мы будем в элементе d[i, j] матрицы, размером n*n, диагональные элементы которой (d[i, i]) равны операндам, а для i > j все элементы равны 0. Пусть мы хотим подсчитать значение арифметического выражения для операндов, начиная с i-го и заканчивая j-м для i < j. Если мы предположим, что последней будет выполняться арифметическая операция, расположенная после операнда с номером k (k < j) и эта операция — сложение, то результат подсчета будет равен сумме элементов d[i, k] и d[k+1, j] нашей матрицы. С умножением ситуация несколько более сложная. Так как операндами могут быть и отрицательные числа, то для нахождения максимума из произведений нужно знать не только максимальные, но и минимальные значения для арифметических операций над операндами с i-го по k-й и с k+1-го по j-й соответственно. Значит для любой последовательности операндов нужно хранить значение как максимально, так и минимально возможного результата выполнения арифметических операций над ними. Однако, дополнительная матрица для хранения минимальных значений не нужна. Так как для i > j матрица d не заполнена, мы можем отвести эти элементы для хранения минимумов, только запоминать результат решения этой подзадачи для операндов, начиная с i-го и заканчивая j-м, мы будем в элементе d[j, i]. Тогда в общем случае, если после k-го операнда стоит операция умножения, то максимальный результат будет равен max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] * d[k+1][j]));
+
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <tex>i</tex>-го и заканчивая <tex>j</tex>-м. Запоминать результат оптимального решения соответствующей подзадачи мы будем в элементе <tex>d[i, j]</tex> матрицы, размером <tex>n\times n</tex>, диагональные элементы которой <tex>(d[i, i])</tex> равны операндам, а для <tex>i > j</tex> все элементы равны <tex>0</tex>. Пусть мы хотим подсчитать значение арифметического выражения для операндов, начиная с <tex>i</tex>-го и заканчивая <tex>j</tex>-м для <tex>i < j</tex>. Если мы предположим, что последней будет выполняться арифметическая операция, расположенная после операнда с номером <tex>k (k < j)</tex> и эта операция — сложение, то результат подсчета будет равен сумме элементов <tex>d[i, k]</tex> и <tex>d[k+1, j]</tex> нашей матрицы. С умножением ситуация несколько более сложная. Так как операндами могут быть и отрицательные числа, то для нахождения максимума из произведений нужно знать не только максимальные, но и минимальные значения для арифметических операций над операндами с <tex>i</tex>-го по <tex>k</tex>-й и с <tex>k+1</tex>-го по <tex>j</tex>-й соответственно. Значит для любой последовательности операндов нужно хранить значение как максимально, так и минимально возможного результата выполнения арифметических операций над ними. Однако, дополнительная матрица для хранения минимальных значений не нужна. Так как для <tex>i > j</tex> матрица <tex>d</tex> не заполнена, мы можем отвести эти элементы для хранения минимумов, только запоминать результат решения этой подзадачи для операндов, начиная с <tex>i</tex>-го и заканчивая <tex>j</tex>-м, мы будем в элементе <tex>d[j, i]</tex>. Тогда в общем случае, если после k-го операнда стоит операция умножения, то максимальный результат будет равен <tex>max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] \cdot d[k+1][j]))</tex>;
  
 
== Реализация ==
 
== Реализация ==
   // d - матрица как в описании; a - последовательность из n элементов; i, j, k - счётчики
+
   <font color = "green">// a - заданная последовательность из n элементов</font>
 
    
 
    
   for i := 1 to n do
+
   '''int maxValueOfExpression'''(a, n):
    d[i][i] := a[i];
+
    '''for''' i = 1 '''to''' n:
 +
      d[i][i] = a[i]
 
    
 
    
  for i := n - 1 downto 1 do
+
    '''for''' i = n - 1 '''downto''' 1:
    for j := i + 1 to n do
+
      '''for''' j = i + 1 '''to''' n:
      for k := i to j - 1 do
+
        '''for''' k = i '''to''' j - 1:
        d[i][j] := max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] * d[k+1][j]));
+
          d[i][j] = max(d[i][j], max(d[i][k] + d[k + 1][j], d[i][k] * d[k + 1][j]))
 
+
    '''return''' d[1][n]
  write(d[1][n]); // вывод ответа
+
 
 
== Пример ==
 
== Пример ==
Пусть дана последовательность 2, 1, 1, 2. Таблица <tex>d</tex> для неё будет выглядеть так:
+
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
+
 
|-
+
:{| border = 1; class="wikitable"
| || j = 1 || j = 2 || j = 3 || j = 4
+
|-align = "center"
|-
+
|&nbsp;&nbsp;&nbsp;&nbsp;
| i = 1 || 2 || 3 || 4 || 9
+
|&nbsp;&nbsp;<tex>j = 1</tex>&nbsp;&nbsp;
|-
+
|&nbsp;&nbsp;<tex>j = 2</tex>&nbsp;&nbsp;
| i = 2 || 0 || 1 || 2 || 4
+
|&nbsp;&nbsp;<tex>j = 3</tex>&nbsp;&nbsp;
|-
+
|&nbsp;&nbsp;<tex>j = 4</tex>&nbsp;&nbsp;
| i = 3 || 0 || 0 || 1 || 3
+
|-align = "center"
|-
+
|&nbsp;&nbsp;<tex>i = 1</tex>&nbsp;&nbsp;
| i = 4 || 0 || 0 || 0 || 2
+
|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>3</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>4</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>9</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>0</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>4</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 3</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>0</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>0</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>3</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 4</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>0</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>0</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>0</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;
 +
|}
 +
 
 +
== Восстановление ответа ==
 +
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <tex>d</tex> хранить каким способом был получен оптимальный ответ. То есть будем хранить <tex>index</tex> {{---}} границу раздела на 2 подотрезка <tex>(i \ldots index</tex> и <tex>index + 1 \ldots j)</tex> и <tex>operation</tex> {{---}} операцию совершенную над двумя отрезками (<tex>+, \times</tex>). В итоге для каждого отрезка мы будем знать какой знак и куда поставить. Для простоты будем заключать каждый полученный подотрезок в скобки. Таким образом мы получим выражение, в котором полностью расставлены скобки.
 +
 
 +
Для вышеприведенного примера таблица будет выглядеть так:
 +
 
 +
:{| border = 1; class="wikitable"
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>index</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 3</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 4</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>3</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 3</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>3</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 4</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;
 +
|}
 +
 
 +
:{| border = 1; class="wikitable"
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>operation</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 3</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>j = 4</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 1</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>+</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>\times</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>\times</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 2</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>+</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>\times</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 3</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;<tex>+</tex>&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;<tex>i = 4</tex>&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 +
|&nbsp;&nbsp;&nbsp;&nbsp;
 
|}
 
|}
  
== Источники ==
+
После того, как посчитана динамика, можно рекурсивно восстановить ответ:
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. - 300стр. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
+
*Если длина текущего отрезка равна <tex> 1 </tex>, выходим из рекурсии
http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm
+
*Оборачиваем текущий отрезок <tex> l \ldots r </tex> в скобки
*
+
*Ставим после элемента последовательности на позиции <tex> d[l][r].index </tex> знак <tex> d[l][r].operation </tex>
 +
*Рекурсивно запускаем от отрезков <tex> l \ldots d[l][r].index </tex> и <tex> d[l][r].index + 1 \ldots r </tex> 
 +
 
 +
Таким образом ответ <tex> ((2+1)\times(1+2))</tex>
 +
 
 +
== Решение задачи без возможности использования скобок ==
 +
При условии задачи, в котором запрещено использовать скобки, вышеописанный алгоритм будет работать некорректно. Дело в том, что если на отрезке <tex>k\ldots j</tex> была использована операция сложения, то мы не можем перемножить результаты на отрезке <tex>i\ldots k - 1</tex> и отрезке <tex>k\ldots j</tex>. Для решения этой проблемы будем использовать две матрицы <tex>d</tex> {{---}} такую же как и раньше, а также <tex>p</tex> <tex>(p[i][j]</tex> {{---}} произведение чисел <tex dpi = "130">a_i, a_{i+1}, \ldots, a_j)</tex>.  Тогда получим новую формулу пересчета динамики:
 +
<br />
 +
* <tex>d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k] + d[k + 1][j],  p[i][k] \cdot p[k + 1][j])] \ (i < j)</tex> <br />
 +
 
 +
== См. также ==
 +
*[[Задача о порядке перемножения матриц | Задача о порядке перемножения матриц]]
 +
*[[Задача о наибольшей общей подпоследовательности | Задача о наибольшей общей подпоследовательности]]
 +
 
 +
== Источники информации==
 +
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]
 +
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]

Текущая версия на 19:07, 4 сентября 2022

Задача:
Пусть задана последовательность неотрицательных чисел [math]a_1, a_2, \ldots, a_n \ (a_i \geqslant 0)[/math]. Требуется расставить знаки [math]+, \times[/math] и скобки в последовательности, чтобы значение полученного арифметического выражения было максимальным.


Решение

Данная задача решается с использованием принципа оптимальности на подотрезках. Введём матрицу [math]d[/math] размером [math]n \times n[/math], где [math]d[i][j][/math] будет равен максимальному значению, достигаемому на подотрезке [math]a_i, a_{i+1}, \ldots, a_j[/math]. Получаем следующие соотношения:

  • [math]d[i][i] = a_i [/math]
  • [math]d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k] \cdot d[k+1][j])] \ (i \lt j)[/math]

Вычислим элементы таблицы [math]d[/math], тогда ответом на задачу будет значение [math]d[1][n][/math].

Доказательство

Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции [math]+[/math] и [math]\times[/math], расставить скобки так, чтобы результат оказался максимальным. Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с [math]i[/math]-го и заканчивая [math]j[/math]-м. Запоминать результат оптимального решения соответствующей подзадачи мы будем в элементе [math]d[i, j][/math] матрицы, размером [math]n\times n[/math], диагональные элементы которой [math](d[i, i])[/math] равны операндам, а для [math]i \gt j[/math] все элементы равны [math]0[/math]. Пусть мы хотим подсчитать значение арифметического выражения для операндов, начиная с [math]i[/math]-го и заканчивая [math]j[/math]-м для [math]i \lt j[/math]. Если мы предположим, что последней будет выполняться арифметическая операция, расположенная после операнда с номером [math]k (k \lt j)[/math] и эта операция — сложение, то результат подсчета будет равен сумме элементов [math]d[i, k][/math] и [math]d[k+1, j][/math] нашей матрицы. С умножением ситуация несколько более сложная. Так как операндами могут быть и отрицательные числа, то для нахождения максимума из произведений нужно знать не только максимальные, но и минимальные значения для арифметических операций над операндами с [math]i[/math]-го по [math]k[/math]-й и с [math]k+1[/math]-го по [math]j[/math]-й соответственно. Значит для любой последовательности операндов нужно хранить значение как максимально, так и минимально возможного результата выполнения арифметических операций над ними. Однако, дополнительная матрица для хранения минимальных значений не нужна. Так как для [math]i \gt j[/math] матрица [math]d[/math] не заполнена, мы можем отвести эти элементы для хранения минимумов, только запоминать результат решения этой подзадачи для операндов, начиная с [math]i[/math]-го и заканчивая [math]j[/math]-м, мы будем в элементе [math]d[j, i][/math]. Тогда в общем случае, если после k-го операнда стоит операция умножения, то максимальный результат будет равен [math]max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] \cdot d[k+1][j]))[/math];

Реализация

 // a - заданная последовательность из n элементов
 
 int maxValueOfExpression(a, n):
   for i = 1 to n:
     d[i][i] = a[i]
 
   for i = n - 1 downto 1:
     for j = i + 1 to n:
       for k = i to j - 1:
         d[i][j] = max(d[i][j], max(d[i][k] + d[k + 1][j], d[i][k] * d[k + 1][j]))
   return d[1][n]

Пример

Пусть дана последовательность [math]2, 1, 1, 2[/math]. Таблица [math]d[/math] для неё будет выглядеть так:

       [math]j = 1[/math]     [math]j = 2[/math]     [math]j = 3[/math]     [math]j = 4[/math]  
  [math]i = 1[/math]     [math]2[/math]     [math]3[/math]     [math]4[/math]     [math]9[/math]  
  [math]i = 2[/math]     [math]0[/math]     [math]1[/math]     [math]2[/math]     [math]4[/math]  
  [math]i = 3[/math]     [math]0[/math]     [math]0[/math]     [math]1[/math]     [math]3[/math]  
  [math]i = 4[/math]     [math]0[/math]     [math]0[/math]     [math]0[/math]     [math]2[/math]  

Восстановление ответа

С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице [math]d[/math] хранить каким способом был получен оптимальный ответ. То есть будем хранить [math]index[/math] — границу раздела на 2 подотрезка [math](i \ldots index[/math] и [math]index + 1 \ldots j)[/math] и [math]operation[/math] — операцию совершенную над двумя отрезками ([math]+, \times[/math]). В итоге для каждого отрезка мы будем знать какой знак и куда поставить. Для простоты будем заключать каждый полученный подотрезок в скобки. Таким образом мы получим выражение, в котором полностью расставлены скобки.

Для вышеприведенного примера таблица будет выглядеть так:

  [math]index[/math]     [math]j = 1[/math]     [math]j = 2[/math]     [math]j = 3[/math]     [math]j = 4[/math]  
  [math]i = 1[/math]     [math]-[/math]     [math]1[/math]     [math]1[/math]     [math]2[/math]  
  [math]i = 2[/math]     [math]-[/math]     [math]-[/math]     [math]2[/math]     [math]3[/math]  
  [math]i = 3[/math]     [math]-[/math]     [math]-[/math]     [math]-[/math]     [math]3[/math]  
  [math]i = 4[/math]     [math]-[/math]     [math]-[/math]     [math]-[/math]     [math]-[/math]  
  [math]operation[/math]     [math]j = 1[/math]     [math]j = 2[/math]     [math]j = 3[/math]     [math]j = 4[/math]  
  [math]i = 1[/math]          [math]+[/math]     [math]\times[/math]     [math]\times[/math]  
  [math]i = 2[/math]               [math]+[/math]     [math]\times[/math]  
  [math]i = 3[/math]                    [math]+[/math]  
  [math]i = 4[/math]                      

После того, как посчитана динамика, можно рекурсивно восстановить ответ:

  • Если длина текущего отрезка равна [math] 1 [/math], выходим из рекурсии
  • Оборачиваем текущий отрезок [math] l \ldots r [/math] в скобки
  • Ставим после элемента последовательности на позиции [math] d[l][r].index [/math] знак [math] d[l][r].operation [/math]
  • Рекурсивно запускаем от отрезков [math] l \ldots d[l][r].index [/math] и [math] d[l][r].index + 1 \ldots r [/math]

Таким образом ответ [math] ((2+1)\times(1+2))[/math]

Решение задачи без возможности использования скобок

При условии задачи, в котором запрещено использовать скобки, вышеописанный алгоритм будет работать некорректно. Дело в том, что если на отрезке [math]k\ldots j[/math] была использована операция сложения, то мы не можем перемножить результаты на отрезке [math]i\ldots k - 1[/math] и отрезке [math]k\ldots j[/math]. Для решения этой проблемы будем использовать две матрицы [math]d[/math] — такую же как и раньше, а также [math]p[/math] [math](p[i][j][/math] — произведение чисел [math]a_i, a_{i+1}, \ldots, a_j)[/math]. Тогда получим новую формулу пересчета динамики:

  • [math]d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k] + d[k + 1][j], p[i][k] \cdot p[k + 1][j])] \ (i \lt j)[/math]

См. также

Источники информации