本文共 574 字，大约阅读时间需要 1 分钟。

铺瓷砖、铺地板、在电路板上嵌入芯片等问题，都属于一类问题，基本上可以描述为在一个 N × M 的平面空间中摆放一些形状固定的物品，要求覆盖整个平面空间，问有多少种摆放方法。在某些情况下还会增加一点难度，比如在平面上标记一些位置为“坏”点，摆放物品时要避开这些位置等。这类问题传统上是使用状态压缩的动态规划方法解题，因状态递推关系复杂，常用深度优先搜索（DSF）辅助状态的遍历。近些年也流行使用轮廓线动态规划方法求解，但其本质上还是状态压缩。这一课我们就用传统的状态压缩动态规划方法解决铺瓷砖问题。

问题分析

铺瓷砖（地板）问题通常以格子为单位给出 N × M 这样的类似棋盘的平面空间，通常 N 或 M 中的一个明显小于另一个，比如本课要讲的题目：有一块面积为 N × M （N ≤ 6、M ≤ 500）的房间，现在有面积为 1 × 2 和 2 × 1 的地板无数个，要给整个房间铺上地板，有多少种铺地板的方法？题目给出了一个例子，就是当 N = 4、M = 2 的情况，共有 5 种铺法：

图（1）4 × 2 的面积铺地板的 5 种方法

当看到题目中给出的某个维度明显偏小的时候，就应该知道这可能要用到状态压缩了。为什么这么说呢？因为题目的状态往往是呈几何级数增加的，以铺瓷砖问题为例，状态个数是 $2^N$ 个，如果 N 太大，用于表示压缩的状

转载地址：http://adcgj.baihongyu.com/