Недавно я столкнулся с этим вопросом: «Вам дано логическое выражение, состоящее из строки символов« истина »,« ложь »,« и »,« или »и« xor ». Подсчитайте количество способов заключить в скобки Выражение такое, что оно будет иметь значение true. Например, есть два способа заключить в скобки слова «true и false xor true», чтобы оно получило значение true ».
Я знал, что это проблема динамического программирования, поэтому я попытался найти собственное решение, которое заключается в следующем. Предположим, у нас есть выражение ABC .... D, где '.' представляет любую из операций и, или, xor и заглавные буквы представляют истину или ложь. Допустим, количество способов для этого выражения размера K для получения значения true равно N. При добавлении нового логического значения E к этому выражению есть два способа заключить это новое выражение в скобки 1. ((ABC .... D) .E) т.е. со всеми возможными скобками ABC .... D мы добавляем E в конце. 2. (ABC (DE)) т.е. сначала оцените DE, а затем найдите количество способов, которыми это выражение размера K может дать истину.
Предположим, что T [K] - это число способов, которым выражение с размером K возвращает true, тогда T [k] = val1 + val2 + val3, где val1, val2, val3 рассчитываются следующим образом.
1) когда E сгруппирован с D.
я) Это не меняет значение D
II) он инвертирует значение D
в первом случае val1 = T [K] = N. (поскольку это сводится к исходному выражению ABC ... D). Во втором случае переоценивают dp [K] со значением D, обратным и равным val1.
2) когда E сгруппировано со всем выражением.
// val2 содержит число 'true', которое E выдаст с выражениями, которые дали 'true' среди всех экземпляров ABC в скобках ...... D i) если true.E = true, то val2 = N
ii) если true.E = false, то val2 = 0
// val3 содержит число 'true', которое E выдаст с выражениями, которые дали 'false' среди всех экземпляров ABC в скобках ...... D
iii) если false.E = true, то val3 = (2 ^ (K-2) - N) = M т.е. число способов, которым выражение с размером K дает ложное значение [2 ^ (K-2) - количество способов заключить в скобки выражение размера K].
iv) если false.E = false, тогда val3 = 0
Это основная идея, которую я имел в виду, но когда я проверил ее решение, http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf, подход был совершенно другим. Может кто-нибудь сказать мне, что я делаю неправильно, и как я могу лучше решить DP, чтобы я мог придумать решения, подобные приведенному выше.
Заранее спасибо.
источник
true and (false xor true) = (true and false) xor true
(легко увидеть, уменьшив оба доfalse xor true
).Ответы:
Ответ, как и во многих вещах, таков:
Практика, практика, практика.
Кстати, я полагаю, что в своем решении вы зашли в тупик, допустив на самом деле тривиальную ошибку: «Есть два способа заключить это новое выражение в скобки» - не больше ли 2? Как насчет
(A.B.(C.D.E))
, например?источник
Я согласен с Occulus, что практика наиболее необходима, и хотел бы добавить, что вам необходимо уделять внимание распознаванию шаблонов в задачах, которые можно решить с помощью DP (это довольно хорошо объясняется в CLRS)
Вы можете найти спой проблемы, связанные с динамическим программированием здесь :)
источник