Недавно я столкнулся с этим вопросом: "Вам дается булевское выражение, состоящее из строки символов" true "," false "," and "," or "и" xor ". Подсчитайте количество способов чтобы заключить в скобки выражение, чтобы оно оценивалось как true. Например, существует два способа вставить в скобки" true и false xor true", чтобы он оценивал значение true.
Я знал, что это проблема динамического программирования, поэтому я попытался придумать решение, которое будет следующим. Предположим, что мы имеем выражение как A.B.C..... D где '.' представляет любую из операций и, или, xor и заглавные буквы представляют true или false. Допустим, что количество путей для этого выражения размера K для создания истины равно N., когда к этому выражению добавляется новое булево значение E, есть два способа скопировать это новое выражение 1. ((ABC.... D).E) т.е. со всеми возможными скобками A.B.C..... D мы добавляем E в конце. 2. (A.B.C. (D.E)) т.е. сначала оцените D.E, а затем найдем количество способов выражения этого выражения размера K.
предположим, что T [K] - количество способов выражения выражения с размером K, тогда T [k] = val1 + val2 + val3, где val1, val2, val3 вычисляются следующим образом.
1), когда E сгруппирована с D.
i) Он не меняет значения D
ii) он инвертирует значение D
в первом случае val1 = T [K] = N. (Поскольку это сводится к исходному выражению A.B.C.... 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" среди всех экземпляров в скобках A.B.C....... D
iii) если false.E = true, то val3 = (2 ^ (K-2) - N) = M ie. количество способов выражения с размером K создает ложь [2 ^ (K-2) - это число способов скобки выражения размера K].
iv), если false.E = false, тогда val3 = 0
Это основная идея, которую я имел в виду, но когда я проверил ее решение http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf, подход был совершенно другим. Может кто-то сказать мне, что я делаю неправильно, и как я могу улучшить решение DP, чтобы я мог придумать решения, подобные тому, который был приведен выше.
Спасибо заранее.
