?

题意：题目描述：用1*2 的矩形通过组合拼成大矩形，求拼成指定的大矩形有几种拼法。

?

思路：我看了上面的博客，想了很久才明白是如何处理状态的。

由于是1 * 2，所以可以通过相邻两行的转化关系来推导。

两行铺不铺砖可以用二进制来表示，但是如果暴力枚举，大概有2^10 * 2 ^ 10 次那么多状态（虽然其中有很多状态是没有用的）。

所以采用dfs来枚举各种可行状态：

状态标记 横放和竖放的下一个均为1，竖放的上一个和不放置为0 ，每行可以转化为1个2进制数。当这一行访问结束时，就会得到上一行状态，和该行状态，因为所有情况都是我们设置的，所以pre状态一定会转化为now状态

对于每一个位置，我们有三种放置方法：1. 竖直放置2. 水平放置3. 不放置

d为当前列号 ，初始化d, now, pre都为0。now为当前行，pre为当前行的上一行

1. d = d + 1, now << 1 | 1, pre << 1; // 竖直放置，当前行该列为1，上一行该列置为0

2. d = d + 2, now << 2 | 3, pre<< 2 | 3; // 横放 都为11（因为当两行的状态往下推时，必须要保证pre这一行摆满，所以pre也都为11）

3. d = d + 1, now << 1, pre<< 1 | 1; // 上一行该列置为1，不能竖放，不放置的状态

因为转移状态有很多种，所以用dfs去枚举各种可行的状态。

最后在转移的时候，dp[0][(1 << w) - 1] = 1 表示只有第0行全部铺满才行。只需要算到 h - 1 行，然后 h 行全部铺满为答案。

代码：

?

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include

?

?