基于联通性的状态压缩动态规划是一类很典型的状态压缩动态规划问题，因为其压缩的本质并不像是普通的状态压缩动态规划那样用0或者1来表示未使用、使用两种状态，而是使用数字来表示类似插头的状态，因此，它又被称作插头DP。
插头DP本质上是一类状态压缩DP，因此，依然避免不了其指数级别的算法复杂度，即便如此，它依然要比普通的搜索算法快很多。
【例】Postal Vans（USACO training 6.1.1）
有一个4*n的矩阵，从左上角出发，每次可以向四个方向走一步，求经过每个格子恰好一次，再回到起点的走法数。
【算法分析】
看到此题，许多读者觉得4很小，会想到搜索算法或者是递推公式，而实际上，搜索算法是不能解决此题的，当n稍大一点，搜索算法即使写的再漂亮，也不能通过此题。本题确实有递推公式，但递推公式却不是那么好找，因此，可以考虑使用插头DP。
为了更好的了解插头DP，首先引入以下几个概念：
1.插头
对于矩阵上的任何一个格点，路径总是会穿过它，也就是从一头进入，从一头出去，这样的情况一共有6种，如下所示：
一个合法的路径需要满足的必要条件之一是：它的每一个格子上的路径插头都是上述六者之一，并且要相互匹配。相互匹配的意思是，如果一个格子上方的格子有向下的插头，那么这个格子就必须有向上的插头与它相匹配。
2.轮廓线
对于任何一个未决策的格子，仅有其上边和左边的格子对其的放置方法有影响，因此，可以根据当前已经决策的格子画出一条轮廓线，分割出已经决策和未决策的格子。
如上图就是两种典型的轮廓线，一种是基于格子的轮廓线，当前该转移的是轮廓线拐角处的格子；一种是基于行的轮廓线，当前该转移的是轮廓线下方的一整行。
对于第一种情况，涉及的插头一共有N+1个，其中N个下插头，1个右插头，需要保存的插头数量是N+1个，对于第二种情况，只有N个下插头，需要保存的插头数是N个。
3.连通性
对于这类动态规划问题，除了要保存每一个插头外，还需要记录这些插头的连通性情况。例如，使用[(1,2)(3,4)]来表示该行第1、2个格子已经连通，第3、4个格子已经连通。
如图所示，两者的下插头完全一致，但连通性却完全不同。因此，还需要在状态中表示他们的连通性。
由于插头的表示已经是指数级别的空间，表示连通性如果再需要指数型的空间，那么空间和时间的消耗将是巨大的！因此，需要有更好的办法去表示连通性，通用的一个办法我们称作“括号表示法”。
对于同一行的四个格子，假设他们都有下插头，则，他们的连通性只可能有上图两种情况[(1,2),(3,4)],[(1,4),(2,3)]，而不可能是[(1,3),(2,4)]，更普遍的，因为插头永远都不可能有交叉，因此，任何两个格子之间的联通性也不会存在交叉。这和括号匹配是完全一致的！
括号表示法的基本思想是三进制：
0：无插头状态，用#表示
1：左括号插头，用（表示
2：右括号插头，用）表示
图左（使用格点转移）可以表示为：（（）#）
图右（使用行来转移）可以表示为：（（））
在此基础上，继续来了解插头DP的状态转移方式。
1.基于格点的状态转移：
基于格点的状态转移方式每次转移仅一个格子，转移的时候需要考虑这个格子的左方以及上方是否有插头。
左方和上方只有一个插头。此时，该格必然有一个插头和这个插头匹配，另一个插头插向下方或右方，这个格子相当于延续了之前该插头的连通状态，因此，转移方式是：将插头所在的位不动（插头插向下方）或向右移动一位（插向右方）。
左方有插头，上方有插头。这种情况下相当于合并了两个连通块，需要考虑两个插头的括号表示情况：
case1：”((”，两者都是左插头，此刻要把两个两个连通分量合
case2：”))”，两者都是右插头，此时，合并他们相当于直接把它们变为”##”即可。
case3：”()”，即两者本来就是匹配的，此时，合并他们相当于把它们连起来形成回路，对于需要形成一条回路的题目，只有在最后一个格子形成回路才是合法的转移方式。
其中，左方有插头，上方无插头以及左方无插头，上方有插头的情况十分类似，在实现代码的时候可以合并。
2.基于行的状态转移：
基于行的状态转移，使用搜索的办法实现，dfs每一行的合法状态，然后更新状态至下一行。容易实现但算法复杂度较高，很少有人使用。在此处不再赘述。
需要注意的是，虽然插头DP使用的是三进制的状态表示，但是往往在实现的时候，使用的却是四进制（仅使用0、1、2，3不表示任何意义）。原因是由于计算机本身的设计导致其对2的幂次方进制数计算速度很快，使用四进制可以利用到位运算，加快运行速度。
此外，由于在状态转移的过程中，需要知道每一个左括号所对应的右括号的位置，，由于合法状态是很有限的，因此，可以通过预处理的方式将合法状态以及这些状态下每一个左括号所匹配的右括号的位置记录下来，利用额外空间换来时间复杂度的下降。
本题在读入数据过大的时候会超过long long类型，因此需要用到高精度运算，实现时可以用结构体复写加法运算符的方式来实现。熟悉java的读者也可以直接使用java中的BigInteger类。
用最多的梦面对未来
