6
第4-5课：铺瓷砖问题
source link: https://blog.csdn.net/orbit/article/details/108729357
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
第4-5课：铺瓷砖问题_oRbIt 的专栏-CSDN博客
铺瓷砖、铺地板、在电路板上嵌入芯片等问题，都属于一类问题，基本上可以描述为在一个 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 太大，用于表示压缩的状
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK