算法学习之路|状态压缩dp

动态规划的题目中，状态的表示是解题的关键，。在一些dp问题中，状态可能会非常复杂，导致用来存储状态的dp数组会有很多维。为此，我们需要用过状态压缩来达到减少状态维数的目的。在状态压缩dp中，灵活运用位运算是一项必不可少的要求。

下面举个简单的例子说明怎样缩减dp数组维数：

有一个n*m的棋盘，上面放着一些棋子，如果用1表示坐标为(i.j)的位置有棋子，0表示没有。按照正常思路，我们会用一个二维数组ai存储每一个格子的信息。但是此时我们可以看到，这个二维数组是由0和1组成的，每一行（或列）都可以看成一个二进制数。因此，我们可以用一个一维数组存储每一行（或列）的和棋子信息等价的二进制数，这就达到了缩减维数的目的。

一道例题：有一个mn的棋盘，在上面放12的小方块，要铺满整个棋盘，求有多少种铺法。（由于找不到原题，不清楚能否ac）
详见代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define mod 1000000007
using namespace std;
int dp[34][10005];
//dp[i][state]表示该填充第i行，第i-1行对它的影响是state的时候的方法数
int n,m;
void dfs(int i,int j,int pre,int nex)//i为进行到第i行，j表示进行到第i行的第j个，pre表示上一行对这一行的影响，nex表示这一行对下一行的影响
{
    if(j==n)
    {
        dp[i+1][nex]+=dp[i][pre];//当前行查找完毕时，更新dp数组的值，即表示i+1行状态的个数是第i行状态数的总和，此句是dp数组更新的关键
        return;
    }
    //如果当前位置已经被上一行占用
    if(((1<<(n-j-1))&pre)>0)//位运算的体现
        dfs(i,j+1,pre,nex);
    //如果当前位置空下，尝试竖放方块
    if(((1<<(n-j-1))&pre)==0)
        dfs(i,j+1,pre,nex|(1<<(n-j-1)));//把nex中第n-j位变为1
    //如果当前位为空且后一位也空，横放方块
    if(j+1<n&&((1<<(n-j-1))&pre)==0&&((1<<(n-j))&pre)==0)
        dfs(i,j+2,pre,nex);
    //以当前位为基准时，1*2小方块的放法只有横放在右边或者竖放在下边，因为往上和往左的情况已经被之前的搜索找到过了
    return;
}
int main()
{
    while (cin>>n>>m)
    {
        memset(dp,0,sizeof(dp));
        if (n==0&&m==0) break;
        dp[1][0]=1;//一开始自然自有一种状态且不受上一行影响
        for (int i=1;i<=m;i++)
        {
            for (int j=0;j<(1<<n);j++)
            if (dp[i][j])//如果此种状态可行
            {
                dfs(i,0,j,0);
            }
        }
        cout<<dp[m+1][0]<<endl;
    }
}