crclz
2020-12-24 14:16:29 +08:00
已经一年多没碰 OJ 了...花了 10 分钟想了个思路：
思路：这个问题问的是：“有多少种语法树”。
首先明确一下题目：有 n 个变量。我们简化一下题目，把变量统一换成 i 。
这样，求出的最终结果只需要乘上 n 个元素的全排列数量 A(n,n)，就可以得到最终的答案。
然后我们对语法建模。这个文法可以用经典的表达式文法稍作变形得到：
E -> E op T | T
T -> i | (E op E) // 这里假设不能有(((i)))这种套娃，否则就无限种了
op -> 与 | 或
如果没学过文法，可以用直觉理解：
如果一个式子是“(i & i) | i”，
那么这个式子的语法树的推导为：
E => E op T => T op T => (E op E) op i => (i op i) op i => (i & i) | i 。
每一次我把一个符号扩展的时候，就是建立一个子树的动作。
另外，又因为这个文法不是二义文法，所以得到的答案不会重复。
好了，现在就对这个文法的建模完毕了。
同时注意，op 可以不展开，只需要在最后呈上 2^(运算符个数)就行了。
>>> 我们的任务转换为：求满足条件的语法树的种类。条件：语法树的叶子节点有 N 个 i 。
================= 分割线
好，现在一个笨办法就是，用递归，在每个节点，都对所有可能的子树做尝试。但不能无休止的尝试，应该剪枝。剪枝的方法就是：如果当前的 i 的数量大于 N，那么就 return （剪枝）。
然而，这个办法时间复杂度没有经过优化。
我们可以想到第二种方法：
对于每一个非终结符（ E, T ），维护一个表 table：key=(非终结符, i 的数量)，value=子树种类。
例子：table[('E', 5)]=10 的意思是，以 E 为根节点，满足“有 5 个 i”的语法树的数量为 10.
现在就可以通过 [递推] 来解决了。
===
由于思考时间短暂，文法等推理如果有错误请谅解。（大体的思路是可行的）