这个题目非常赞！ 给定一个矩形，要求用1*2 的格子进行覆盖，有多少种覆盖方法呢？

dp[i][j] 当状态为j，且第i行已经完全铺满的情况下的种类数有多少种？j中1表示占了，0表示没有被占。

很显然，当每行被放了之后，有一些状态是不可能的，我们这里用1 表示竖着放，0表示横着放。 所以两个0 要相邻，这是程序中的s。

我们每一状态转移，枚举每一个可能的状态，我们希望dp[i][j] 中的j呈现出s[k] 的状态，依次来进行状态转移。

#include 
    
     #include 
     
      #include 
      
       using namespace std;vector
       
         s;  // possible statelong long dp[13][1<<12];  // dp[i][j]  the number of (row i state j)int main(){    //freopen("1.txt","r",stdin);    int M,N;    while(cin>>M>>N && M!=0 && N!=0)    {        s.clear();        if(M*N%2) {cout<<0<