Следующая задача взята из главы о динамическом программировании Вазирани и др. др.
[6.6] Определим операцию умножения (×) на трех символах a; б; c в соответствии со следующей таблицей:
Следовательно, a × a = b, a × b = b и т. д.
Найдите эффективный алгоритм, который проверяет строку этих символов, скажем, bbbbac, и решает, можно ли заключить строку в скобки таким образом, чтобы значение результирующего выражения было a. Например, при вводе bbbbac ваш алгоритм должен возвращать yes, потому что ((b(bb))(ba))c = a.
Вот мой подход: сопоставьте его с проблемой подсчета количества логических скобок, как указано здесь< /а>сильный>. В этой задаче вам дано логическое выражение вида
T или F и T xor T
и вам нужно найти количество способов заключить это в скобки, чтобы оно оценивалось как истинное.
Мы можем рассматривать или , и , xor как операторы, которые следуют определенным правилам (T xor F = T и т. д. .) и воздействовать на операнды, принимающие значения T или F. Для нашей исходной задачи мы можем думать об a, b, c как об операндах с умножением (x), как определено данной таблицей, как обеспечивающие правила .
Имеет ли смысл описанный выше подход или есть более простой подход?