一道算法题?

n对括号(),拼成字符串,总共有多少种有效的匹配组合。要求枚举出来,并打印出个数。进一步的,还要给出计数公式。—- 比如: (()()) 是有效的, (()))( 是无效的。
比如三组括号,所有符合条件的有五种:
1:((()))
2:(()())
3:(())()
4:()(())
5:()()()

这是一道算法面试题。经过ACM算法训练的人应该是可以秒杀之的,但未经训练的人的脑袋里是没有存储多少套路的,那应该拿什么来攻克之? 拿元知识背后的实践理论。本文以此为例来尝试解释一下怎么使用元知识。

问题提炼与模型转化

总结与提炼

总结:从左往右,左单括号的个数一定不小于右单括号的个数。

进一步确认,这还是一个充分且必要的描述。所以接下来拿这个说事,就可以完全抽离出原问题的场景,换到另一个关系更清晰的comfort zone里表达了。

抽象与建模

这个是比较偏个性化的地方。同样的刺激源,不同的人会有不同的反应。换成是我的话,我对数学的东西比较敏感。第一反应就是坐标轴上的一条y=x的曲线。准确地说,是y=x的曲线与x轴之间的阴影区域。好了。就这么多了,方法也就跟着图穷匕首见了。

想象一个n*n的网格坐标轴。一只蚂蚁从原点出发,一次只能向上,向右运动一个格子,最终到达{n,n}点,要求不许跨过y=x的直线。

解决问题

问题目标:打印所有的路径。

输入:坐标{0,0},路径初始值用空字符串””表达。
过程:向左,路径字符串追加一个(符号,向右,追加一个)符号。注意别越到边界之外。
输出:在{n,n}处输出当前积攒的路径字符串。

void printParenthesesList(std::string context,int v, int h, int n){
static int cnt = 0;
if(h<n){
printParenthesesList(context+"(",v, h+1,n);
}

if(v<h){
printParenthesesList(context+")",v+1, h,n);
} else {
if(v==n) {
std::cout<<++cnt<<":" << context <<std::endl;
}
}
}

于是 printParenthesesList(“”,0,0,n)代表着结果。

回测与升华

递推公式

$$f(n) = \sum_{k=0}^{n-1}f(k)f(n-1-k)=\frac{C(2n,n)}{n+1}$$,进而得知是[Catalan-OEIS]数.[catalan-wikipedia],[catalan-mathworld],该问题也是[Stack-sortable permutation].

尾递归

另外,意外发现,我的代码本质上是[tail call],嗯,看来我又跟[tail call] 结缘了。不过这次是无心碰到的。

问题的意义

从公式看得出来,问题的时间复杂度是阶乘级别的。所以为啥要打印呢?


解决问题的标准流程

如何面对问题?

尽可能的提炼信息,精简到不能再精简,尽可能的用抽象的符号语言充要的转述出来。

换句话说,就是两件事情:

沉浸到问题场景中,获得足够的感性材料

这一步是直面问题,积攒第一手感性资料的阶段。如若这个都没做好,就着急往后面走,将陷入纠结反复,陷入无意义无建设性的心理行为模式,浪费大量时间,人力物力财力。这个太常见了…

对问题进行抽象描述,转化成模型语言

这个时候,是体现个体差异的时候。动辄秒杀问题的那种”大神级别”的人物其实在此阶段都是没有思维活动,直接套用自己熟悉的旧有模式,甚至直接调取已经序列化好的知识数据库的。

这一步模型语言的建立,直接决定了解决问题所采取的形式,甚至方法。不同的抽象描述,往往直接暗示着某种逻辑形式。

如何着手解决问题?

前面工作做好后,解决方案往往是水到渠成的。个人认为,模型语言无好坏。人们常说的有好坏,那也一定是对问题的感性材料没吸收充分。当然现实中,你也会神奇的发现很多很多的人,其实解决问题的方式是反着来的,是手里先毫无理由的挑选了一个工具,比如锤子,然后找钉子,把问题强制假设成钉子,不像钉子也要设法看成钉子。甚至说服自己,说服别人,用什么角度看问题才更像是钉子。


实际生活中,人们往往因为各种原因,或浮躁,或无知,并不是遵循着这条唯一的捷径来解决问题的。往往第一第二阶段循环穿插。
[Stack-sortable permutation]: https://en.wikipedia.org/wiki/Stack-sortable_permutation
[catalan-OEIS]: http://oeis.org/A000108
[catalan-mathworld]: http://mathworld.wolfram.com/CatalanNumber.html
[catalan-wikipedia]: https://en.wikipedia.org/wiki/Catalan_number
[tail call]: https://en.wikipedia.org/wiki/Tail_call