从hihoCoder的一道题学习状态压缩+dp

首先,给上题目链接:http://hihocoder.com/problemset/problem/1048 ,简要描述如下:

有1个N*M的盘子,要装2*1的蛋糕,问有多少种方法?(结果对1000000007取余,其中2≤N≤1000,3≤M≤5)

最简单的例子如下:

下面我们来分析：

这个题目类属于状态压缩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：为什么要这么计数呢，我觉得应该这样理解：

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

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

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

即当设为1表示对下一行没有任何影响了。

问题2：如何判断当前状态与上一行的状态是否兼容

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

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

从hihoCoder的一道题学习状态压缩+dp

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

{

从hihoCoder的一道题学习状态压缩+dp

那么有可能有两种情况：

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

从hihoCoder的一道题学习状态压缩+dp

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

特别注意：这里的判断的(i,x)一定不是由(i,x-1)位横着铺砖过来的，否则直接x=x+2,就不会来判断(i,x)位了。

问题3：为什么可以使用动态规划算法来解决这个问题？

这就得从动态规划的特性上去找：

(1)最优子结构

用F[i][j]表示第i行j状态铺砖块的方案数，一定等于i-1行所有的能与状态j兼容的状态k的方案的总和。

(2)重复子问题

求F[i][j]即第i行的每一个状态一定要用到第i-1行的各个状态。

问题4：从状态压缩的特点来看，这个算法适用的题目符合以下的条件：

1.解法需要保存一定的状态数据（表示一种状态的一个数据值），每个状态数据通常情况下是可以通过二进制来表示的。这就要求状态数据的每个单元只有两种状态，比如说棋盘上的格子，放棋子或者不放，或者是硬币的正反两面。这样用 0 或者 1 来表示状态数据的每个单元，而整个状态数据就是一个一串 0 和 1 组成的二进制数。

2.解法需要将状态数据实现为一个基本数据类型，比如 int， long等等，即所谓的状态压缩。状态压缩的目的一方面是缩小了数据存储的空间，另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大，比如用 int 来表示一个状态的时候，状态的单元个数不能超过 32（32 位的机器）。

//注:j&(1<<i)的值 可以用二维数组保存起来 
#include <stdio.h>
#include <string.h> 
#define P 1000000007
#define SWAP(a,b) a=b-a+(b=a)
#define FALSE 0
#define TRUE 1

int TestFirstLine(int j,int m){
	int i=0;
	while(i<m){
		if((j & (1<<i)) == 0) //注意打括号 
			i++;
		else if(i==m-1 || !(j & (1<<(i+1))))
			return FALSE;
		else i+=2; 
	}	
	return TRUE;
} 

int TestCompatible(int j,int k,int m){
	int i=0;
	while(i<m){
		if((j & (1<<i)) == 0){
			if((k & (1<<i)) == 0)
				return FALSE;
			else i++; 
		}
		else{
			if((k & (1<<i)) == 0) i++;
			else if(i==m-1 || !((j & (1<<(i+1))) && (k & (1<<(i+1)))))
				return FALSE;
			else i+=2; 
		}
	}
	return TRUE;
}

int main(){
	int n,m,allStates,i,j,k;
	long long dp[1000][32];
	scanf("%d%d",&n,&m);
	if(n<m) SWAP(n,m);//降低时间复杂度 
	allStates=1<<m;
	memset(dp,0,sizeof(dp));
		
	for(j=0;j<allStates;j++)
		if(TestFirstLine(j,m))
			dp[0][j]=1;
			
	for(i=1;i<n;i++)
		for(j=0;j<allStates;j++)
			for(k=0;k<allStates;k++)
				if(TestCompatible(j,k,m)){
					dp[i][j]+=dp[i-1][k];
					dp[i][j]%=P; 
				}
				
	printf("%lld
",dp[n-1][allStates-1]);//最后一行均为1,所以可输出dp[n-1]的任意一个分量 
	return 0;
}

参照:http://blog.csdn.net/lu597203933/article/details/44137277

从hihoCoder的一道题学习状态压缩+dp

相关推荐