前几天翻开noi导刊，看到一题关于用1×2的骨牌密铺矩形的题目，最后一个优化方法是用了这个公式（来自维基百科：http://en.wikipedia.org/wiki/Domino_tiling）。相当牛逼，不多说，上公式：

下面是用Mathematica代入了几个m,n的计算结果：

第一个函数DominoTiling用了FullSimplify，化简后为整数，但是结果也是不好化简的，花费时间很多。(m, n)=(7, 6)都要3.5s……我试着运算(m, n) = (8, 6)，吃了顿饭回来还没算出来，内存几乎全部被占满，任务无法Abort，只能Quit Kernel。

DominoTiling2改用了N，保留8为小数，这下就很快了，O(mn)。

上图，MathKernel耗尽了所有可分配内存