题意：在n ,m 大的格子上铺满1*2的方格，问最多有多少种铺法

一道经典的轮廓线dp，白书上有解析，这里具体分析一下整个过程

下面使用滚动数组，内存的利用率是非常高的

?

?

dp过程是对[i , j] 点的不断更新，使dp[ i, j ]是此点的最优解，很显然子问题的最优解是原问题的必要条件，因此遍历 [ i , j ]得到的dp[i,j] 都是最优解

// 使用dp的条件 ：子问题最优可推出上一层递归问题最优

dp[i , j] 表示 第i行的j状态下 最多铺法

先看一下状态转移过程：

对于[i,j]点，状态转移共有三种：

[i,j]点不放

1、[i,j]点不放时，K9点必须放，不然铺不满，所以只有当K9=1时，转移到二进制为 K8K7K6...K2K1K00这个状态 0就是[i,j]点

?

[i,j]点放???? (我们只需要考虑往上放和往左放，因为现在是求最优解，如此考虑即可)

2、往上放 必须 K9=0 , 转移到 K8K7K6...K1K0 1

3、往左放 ,? 此时必须 K0= 0? &&? K9=1 （表示K9已经放过了，这样才能铺满） 转移到 K8K7K6...K1 1 1

?

几个细节：

1. 所谓的状态转移，在上述中就是 加法

2. 下面第三重for中 k值遍历的是? 以K0为终点的所有状态，而不是以 [i,j]点为终点的状态

3. 恰如2，转移到的状态（蓝色字体）就是以 [i,j] 点为终点的状态

4.程序中的操作其实是：把[i,j-1] 这个点的所有状态转移给 [i,j]?? , 抓住这句就能很快理解代码了

?

1、遍历 [i,j]点

for(i -> n)

for(j-> m)

for( k =0-> (1<

?

k就表示 [i,j] 点前面格子的状态，就是上图绿色格子的状态，k用2进制表示，0表示不放，1表示放了

k= K9 K8 K7 K6 K5...

?

2、根据上述3个状态把[i,j-1] 点的所有状态都转移给 [i,j] 点

3、 根据dp数组含义，结论应该是 dp[ n-1 ][ (1<

 #include   
#include   
#define N 12   
#define ll long long   
ll dp[2][1< 
 
?