有同学问我砌墙的思路，评论里也有问的，这里说一下我当时的思路吧：

设

为砌规格为 $M\times N$ 的墙的总砌法数，用DP方法在一维递推，很容易得到

。因为不同高度的层与层是不影响的，根据乘法原理有

。

再设

为规格为 $M\times N$ 不带缝的并且内部不含有任何从顶到底线段的砌法之和。我们考虑出现从顶到底的线段的砌法：如果我们允许内部出现线段，那么最后一条线段出现在水平位置为 $k(1\le k < N)$ 的地方的砌法为：

(水平位置小于

的部分任意摆放，后面的则必.须无缝)。由于在

不同时的情况是互斥的，我们有

$f(M,N)=g(M,N)+\sum_{k=1}^{N-1}f(M,k)g(M,N-k)$ ，则我们的递推公式为

$g(M,N)=f(M,N)-\sum_{k=1}^{N-1}f(M,k)g(M,N-k)$ ,DP即可。

创作者周榜