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

9

Недавно я столкнулся с этим вопросом: «Вам дано логическое выражение, состоящее из строки символов« истина »,« ложь »,« и »,« или »и« 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).
Питер Тейлор
Отличный вопрос! Я тоже должен поправиться в DP. Некоторые говорят: «Ах .. DP - это просто простая рекурсия». Это не!
Флоренс Целай
@Florents Tselai только что увидел ваш комментарий. Почему вы думаете, что нет?
Джон Донн

Ответы:

9

Ответ, как и во многих вещах, таков:

Практика, практика, практика.

Кстати, я полагаю, что в своем решении вы зашли в тупик, допустив на самом деле тривиальную ошибку: «Есть два способа заключить это новое выражение в скобки» - не больше ли 2? Как насчет (A.B.(C.D.E)), например?

occulus
источник
"Как мне лучше делать X?" - "Делай Х!" ... звучит разумно ;-)
Йоахим Зауэр
2

Я согласен с Occulus, что практика наиболее необходима, и хотел бы добавить, что вам необходимо уделять внимание распознаванию шаблонов в задачах, которые можно решить с помощью DP (это довольно хорошо объясняется в CLRS)

Вы можете найти спой проблемы, связанные с динамическим программированием здесь :)

nischayn22
источник
Пожалуйста, прокомментируйте, прежде чем downvote, чтобы я мог улучшить :)
nischayn22
эта ссылка не работает!
Диби