编程之美之瓷砖覆盖地板

这个题目的题意很容易理解，在一个N*M的格子里，我们现在有两种类型的 砖块，1 * 2 和 2 * 1，问一共有多少种方案，可以将整个N*M的空间都填满。

最简单的例子就是下面的了：

编程之美中题目：

某年夏天,位于希格玛大厦四层的微软亚洲研究院对办公楼的天井进行了一次大 规模的装修.原来的地板铺有 N×M 块正方形瓷砖,这些瓷砖都已经破损老化了,需要予以 更新.装修工人们在前往商店选购新的瓷砖时,发现商店目前只供应长方形的瓷砖,现在的 一块长方形瓷砖相当于原来的两块正方形瓷砖, 工人们拿不定主意该买多少了, 读者朋友们 请帮忙分析一下:能否用 1×2 的瓷砖去覆盖 N×M 的地板呢?

我们在这里指分析第一个陈述，其实第二个陈述是一样的思路：

这个题目类属于状态压缩DP，对于状态压缩DP，其实最简单的理解就是把状态用比特位的形式表示出来，我们会在下面用例子来说明。

假如现在我们在铺砖 位置(i, j), 并且假设之前的位置已经铺设好的了，在这个位置，我们的选择：

1. 不用铺砖了，可能在(i-1, j)的时刻已经被竖着铺上了，然后考虑的是（i， j+1）
2. 横铺砖，将(i, j+1）也铺上了，然后考虑的是(i, j+2)

3. 竖着铺砖，（将i，j）和（i+1，j）铺上一个竖立的转头。

所以我们如下翻译我们的选择，在位置(i, j) 如果我们选择横着贴砖，那么将(i, j), (i, j+1)都填写成1， 如果竖着贴砖，我们将(i,j)填写成0， 将(i+1, j)填写成1.

为什么要这么计数呢，我觉得应该这样理解：

1. 在横着贴砖的时候，(i, j), (i, j+1) 都是1，这个值其实对下一行如何选择没有影响。

2. 竖着贴砖的第二个，我们也选择了1， 因为这个砖头结束了，对下一行如何选择依然没有影响。

3. 而竖着的第一个砖头，这个砖头是对下面有影响的，如果(i,j)是0，那么(i+1, j)只有是1的情况下才能满足条件。

（这涉及到接下来的 状态兼容性问题）

对于竖着贴砖为什么这样选择，这样选择的一个好处是，我们在处理最后一行的时候，可以保证最后一行都是1， 因为最后一行绝对不能成为 竖砖开始，所以很容易取得最后的解。

好了，我们把这样理解的方案画成图：

 

如果我们将每一行都理解成一个二进制数字，那么

Row1 = 51,  Row2 = 15, Row3 = 48, Row4 = 63, Row5 = 51, Row6 = 63.

最后转头铺满的状态，一定是最后一行全是1。

我们用DP(i,j) 表示如下含义： 当第i行，达到状态j的时候，所能采取的方案数目。 所以明显我们的最后目的是求 DP(N, 2^(M-1)-1);

我们再来简单的分析一下为什么问题可以满足动态规划， 加入现在分析的对象是 DP(i,j)， 那么这一行有多少种铺设办法是和上一行相关的，

如果上一行的某个状态DP(i-1,k) 可以达到 DP(i, j) 我们认为这两个状态是兼容的，如果DP(i-1,k)和DP(i, j)兼容并且 DP(i-1, k)有S中铺设方案，那么DP(i, j)就可以从DP(i-1, k)

这条路径中获得S个方案。 当然这里k的取值可以是 0 ~~~~ 2^(M-1) -1种取值。

现在我们来理解一下，什么叫做 j, k 兼容。

其实我们在上面已经基本给出分析， 如果我们现在铺设 (i,x) x这里表示第i行，第x列

1. 如果值 i  行，j 在x位上的值是0， 那么第 i-1行，j的值在x位上一定是1。因为不可能在同一列相邻的位置铺两个竖着的 第一个，如果满足下一步测试的是(i, x+1), 否则直接返回不兼容。

2. 如果值 i  行，j在x位置的值是1 .

{

            那么有可能有两种情况：

            1. (i-1, x)是0， 这个时候一定是竖着铺设了，下一步检测的是(i, x + 1)

           

            2.  (i-1, x) 是1， 如果是这样的话，那么(i, x)一定是要选择横着铺了，那么(i,x+1)也一定是1，并且(i-1, x + 1)一定是1（如果是0，就是竖着铺了），如果不满足就返回不兼容，满足条件 就测试(i, x + 2)

              

}

对于第一行的兼容性，我们要做一下特别的分析，在第一行中，要么放0， 要么放1。

加入当前测试的是 DP(0, j)的第 x的比特位，即第0行，x列

1. 如果x是1，那么 x + 1 也一定是1，然后测试到 x + 2

2. 如果x是0， 那么直接测试下一个 x + 1

补充说明一点，当测试循环中，我们有时候必须要移动 1 位，有时候移动2位，当需要移动2位并且 x == M - 1(M列数）的时候，说明已经不可能兼容了。
根据上面的分析就不难写出代码了：

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <algorithm>
using namespace std;


#define MAX_ROW 11
#define MAX_STATUS 2048
long long DP[MAX_ROW][MAX_STATUS];
int g_Width, g_Height;

bool TestFirstLine(int nStatus) //test the first line
{
    int i = 0;
    while( i < g_Width)
    {
        if(nStatus & (0x1 << i))
        {
            if( i == g_Width -1 || (nStatus & (0x1 << (i+1))) == 0)
            {
                return false;
            }
            i += 2;
        }
        else
        {
            i++;
        }
    }
    return true;
}

bool CompatablityTest(int nStatusA, int nStatusB) // test if status (i, nStatusA) and (i-1, nStatusB) is compatable.
{
    int i = 0;

    while( i < g_Width)
    {
        if( (nStatusA & (0x1 << i)) == 0)
        {
            if((nStatusB & (0x1 << i)) == 0)
            {
                return false;
            }
            i++;
        }
        else
        {
            if((nStatusB & (0x1 << i)) == 0 )
            {
                i++;
            }
            else if( (i == g_Width - 1) || ! ( (nStatusA & (0x1 << (i+1))) && (nStatusB & (0x1 << (i + 1)))) )
            {
                return false;
            }
            else
            {
                i += 2;
            }

        }
    }
    return true;
}
int main()
{
    int i,j;
    int k;
    while(scanf("%d%d", &g_Height, &g_Width) != EOF )
    {
        if(g_Width == 0 && g_Height == 0)
        {
            break;
        }

        if(g_Width > g_Height)
        {
            swap(g_Width, g_Height);
        }


        int nAllStatus = 2 << (g_Width-1);
        memset(DP, 0, sizeof(DP));
        for( j = 0; j < nAllStatus; j++)
        {
            if(TestFirstLine(j))
            {
                DP[0][j] = 1;
            }
        }

        for( i = 1; i < g_Height; i++)
        {
            for( j = 0; j < nAllStatus; j++)// iterate all status for line i
            {
                for( k = 0; k < nAllStatus; k++) // iterate all status for line i-1
                {
                    if(CompatablityTest(j, k))
                    {
                        DP[i][j] += DP[i-1][k];
                    }
                }
            }
        }
        printf("%lld\n", DP[g_Height-1][nAllStatus - 1]);
    }
    return 0;
}

思路二：
思路：用2进制的01表示不放还是放，第i行只和i-1行有关，枚举i-1行的每个状态，推出由此状态能达到的i行状态：如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块，所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态。然后用dfs搜索在i行放横着的方块的所有可能，并且把这些状态累加上i-1的出发状态的方法数，如果该方法数为0，直接continue。

#include <stdio.h>
#include <string.h>

/** n * m 的地板 */
int n,m;

/** dp[i][j] = x 表示使第i 行状态为j 的方法总数为x */
__int64 dp[12][2049];

/* 该方法用于搜索某一行的横向放置瓷砖的状态数,并把这些状态累加上row-1 行的出发状态的方法数
* @name row 行数
* @name state 由上一行决定的这一行必须放置竖向瓷砖的地方，s的二进制表示中的1 就是这些地方
* @name pos 列数
* @name pre_num row-1 行的出发状态为~s 的方法数
*/
void dfs( int row, int state, int pos, __int64 pre_num )
{
/** 到最后一列 */
if( pos == m ){
dp[row][state] += pre_num;
return;
}

/** 该列不放 */
dfs( row, state, pos + 1, pre_num );

/** 该列和下一列放置一块横向的瓷砖 */
if( ( pos <= m-2 ) && !( state & ( 1 << pos ) ) && !( state & ( 1 << ( pos + 1 ) ) ) )
dfs( row, state | ( 1 << pos ) | ( 1 << ( pos + 1 ) ), pos + 2, pre_num );
}
int main()
{
while( scanf("%d%d",&n,&m) && ( n || m ) ){
/** 对较小的数进行状压，已提高效率 */
if( n < m ){
n=n^m;
m=n^m;
n=n^m;
}

memset( dp, 0, sizeof( dp ) );

/** 初始化第一行 */
dfs( 1, 0, 0, 1 );

for( int i = 2; i <= n; i ++ )
for( int j = 0; j < ( 1 << m ); j ++ ){
if( dp[i-1][j] ){
__int64 tmp = dp[i-1][j];

/* 如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块，
* 所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态
*/
dfs( i, ( ~j ) & ( ( 1 << m ) - 1 ), 0, tmp ) ;
}
else continue;
}

/** 注意并不是循环i 输出 dp[n][i]中的最大值 */
printf( "%I64d\n",dp[n][(1<<m)-1] );

}
return 0;
}