首先我们看一下描述：
这里有张图配合描述：
这里用到了状态压缩动态规划，分析一下这个算法过程。也就是步骤化。
本算法中需要定义的几个概念
1，每行状态（state）
用一个二进制的数字表示，如果某位为0，则意味着该行未被占用，如果为1，则表示已被占用。例如（011000），则表示有4个空位。
2，可用状态枚举（usableEnum）
对每行按位状态取反（~），同时依次去掉每一个的一个1，直至到全为0的情况，则得到一个可用状态的枚举。例如可用状态为10001，则可用状态枚举为01110，01100，01010，00110，01000，00010，00100，00000。这里需要用到一个位运算的公式，即
for(x=s;;x=s&(x-1)){
if(x=0) break;
}
在这里顺便对这个公式进行证明：
命题：for(x=s;;x=s&(x-1))可以逐步去掉s中的1，得到可用状态枚举.
运用数学归纳法，假设原二进制串为s
第一次进行操作时，x=s，x=s&(x-1),得倒的x就是去掉最靠右的那个1，假设成立。
若进行第n次操作后，得到的x是去掉了原二进制串s中的k个1之后的串s'
那么对于第n+1次操作，用s'-1得到的串s'',具有一个性质：即s''等于s'最右的一个1变成0，然后其靠右的所有0皆为1.此时s&s''则会将刚才s'中最靠右的那个1变成0，其他位保持不变。假设成立。
这里有点复杂，需要配图讲解。
3,摆放策略（tactic）
针对当前处理的一行，我们会有一系列的骨牌摆放策略，注意我们并不能事先知道当前策略能否使最终结果最大，所以我们需要迭代符合当前行以及上一行的所有摆放策略，从中得倒一个最佳策略并存储。这里摆放策略的集合是根据可用状态枚举（usableEnum）和上一行的损坏情况进行某种位运算操作得倒的。
算法的步骤分解
在定义完以上三个概念后，我们就能用动态规划的思路来尝试解决问题，如果对上述三个概念还不是特别理解，请耐心继续往下看，本文会通过逐步分解的方式把算法思路讲清楚，在这个分解过程中，自然就能理解为什么需要以上三个概念。
从上图中我们可以看到，一个棋盘中所有格子的占用情况。在这里我们决定从下往上（即从最后一行开始）的求解我们的骨牌摆放策略，实际上你也可以从第一行开始往下进行求解，思路是一样的。
根据动态规划的思想，我们需要将原复杂问题逐步分解成许多较为简单的小问题，而每一个小问题的解决依赖之前已经解决问题的答案，这是动态规划算法的核心思路。
所以首先我们假设，当我们处理到第5行的时候，第6行一直到最后一行的所有可行的最大骨牌策略我们都已经知道，那么我们就可以利用这些已知的信息来求解第5行到最后一行的最大骨牌策略。
首先我们已知第五行的改行状态为：000100，这表示第五行有一个格子是损坏的，而其他格子均可摆放多米诺骨牌。这个时候我们就会自然而然去考虑我们该如何在第五行摆放我们的骨牌，是横着摆还是竖着摆？横着摆几个？竖着摆几个？横着摆还好，因为不会影响其他行，竖着摆说不定下一行对应的位置是个损坏格或者被其他骨牌占用了，根本摆不了。
实际上这些问题都不是问题，注意我们现在假设了我们已经知道了第六行到最后一行所有的占用状态的最大摆放块数，所以我们决定按照以下思路来进行计算。
首先我们根据第五行的状态state：000100，求出第五行的可用状态枚举，求出的公式之前讲过了，这里直接给出答案：{111011，111010，111001，110011，101011，011011，011010，011001，010011，001011，001010，001001，000011，000010，000001，000000}
这里应该对可用状态枚举usableEnum有了一个概念，即当前行所有可行的格子占用方案，注意我这里采用的描述“格子占用方案”，而不是“骨牌铺设方案”，这两者很容易混淆。“格子占用方案”是指，我只知道这个一行的这几个格子是铺了多米诺骨牌的，但是具体是横着铺的还是竖着铺的我并不关心，也就是关注点在格子本身的占用情况上。而“骨牌铺设方案”是指，这一行我的骨牌哪几张是竖着铺，哪几张是横着铺的，关注点在骨牌的摆放位置以及方向上。
在理解了可用状态枚举的概念后，自然会产生一个问题，我们已知了第五行的可用状态枚举后，在这些格子占用方案中，到底哪一种方案会使得从第五行到最后一行能够铺设得多米诺骨牌数量最多？这里你可能又有点迷惑，为什么是第五行到最后一行？时刻记住我们在进行动态规划，我们正是要通过计算出第五行到最后一行的最优解，提供给第四行，从而让第四行能计算出从第四行到最后一行的最优解，这样一直迭代到第一行，那么问题的最终解就得出了。
回到问题本身，显然在第五行的这么多格子占用方案中，我们是无法知道哪个会是最优的，所以我们的思路很暴力，那就是一个个的试，从里面找到最大的。
这种一个一个试的方式看上去很笨拙，但是如果没有一些限定条件你也无法获取最优解，也就是我们该如何判断A方案优于B方案？这种找到判断方案优劣条件的过程，在动态规划的术语中叫“状态转移方程”。
接下来我们来举例判断一下，我们从第五行的可用状态枚举中选两个方案来比较一下优劣，比如111010和000011这两个格子占用方案。（一定要理解这个可用状态枚举和每行状态state的区别，他们都是二进制表示，但是意义是完全不同的，在state中，1表示格子不可用，0表示格子可用，而在usableEnum中，1表示此处能放（具体横着放竖着放不关心）骨牌，0表示此处不能放骨牌，这两个概念如果混淆了你将什么也看不懂）。
首先第五行如果是111010这样一个格子占用方案，这意味着我们在第五行最多能放4块骨牌。也就是那四个1的位置我们全部竖着放骨牌，当然我们可能也放不了4块，因为可能第六行对应的位置是个损坏格，导致我们竖着放根本就放不进去。我知道有部分人可能会问，那我竖着放会不会占用了第四行的格子呢？还是再提醒一次，在动态规划看来，现在第四行就是不存在的，也就是在处理第五行的时候他只会去占用第六行的格子。这里好好在体会一下。
于是我们用这样的逻辑计算第五行采用111010这个格子占用方案的最优解：
1，获取第六行的state，从图3中可以知道，是001001.
2，对第六行状态按位取反，~001001 = 110110.
3，用111010 & 110110（做位与运算），得倒110010.，令其为S
在继续后续步骤之前，我先解释一下以上三个步骤的意义。第一步不用多说，第二步对第6行的状态取反，得到了第6行的可铺设格子方案。类比可用状态枚举感受一下，这一步的操作是为了便于第三步的位与运算。第三步将第五行当前选择的格子铺设方案和第六行的可铺设格子方案做与运算，可以得倒一个实际可行的方案，这个方案告诉我们，原本我们以为第五行最多可以竖着放4块骨牌，但是实际上只能竖着放3块，因为第6行中有一个损坏格子给顶死了，导致第五行对应位置想竖着放骨牌的时候塞不进去。
以上三步骤就是为了得倒一个实际可行的方案，不明的反复仔细看一下。
4，统计S中1的个数，也就是竖着放的骨牌个数。用变量stand表示。
5，对S取反，然后和第五行的格子占用方案111010做&运算。也就是001101&111010 = 001000，统计001000中1有几对，即为横着放的骨牌个数，用变量lay表示。这里为什么能够通过这种位运算得到横着放的骨牌个数我到时候补充解释，这里解释起来有点麻烦。暂时先记住这个方法。
6，用S和第六行的状态state做或运算，即 S | 001001 = 111011，也就是把第五行竖着放的格子占用的第六行的格子计算上，得到了当第5行采用S这个方案时，第6行的格子占用状态。由于我们假设我们已知第6行的各种占用方案的最优解，且存到了一个名为dp数组中，这个数组是个二维数组，这个数组中存储着已知的各种格子占用方案的最优解，横轴是行数，纵轴是改行的格子占用状态，比如dp[6][111011]中存储的值就是当第6行的格子占用情况是111011，第6行到最后一行的最大骨牌摆放数量。
7，我们将stand、lay、dp[6][111011]这三个值相加，当第五行竖着摆三个骨牌，横着摆0个骨牌时，第五行到最后一行的最大骨牌摆放数量，将这个数和max比较（这个max值初始为0），如果该数大于max则更新max，反之什么也不做。
8，去掉S中的一个1（用概念2中那个去1公式），回到第4步骤。直到S = 0。
9，当步骤4到步骤8循环完毕后，我们会得到当第五行格子占用方案为111010时的最大骨牌块数max，将其写入二维数组dp[5][111010]中。
然后我们再将第5行状态设置为000011，重新走上面9个步骤，就会得到我们会得到当第五行格子占用方案为000011时的最大骨牌块数max，将其写入dp[5][000011]中。
