编程兔暑假3.5阶段集训Day6——状压（状态压缩）dp、dp优化以及图论 ...

        今天我们先来讲一下状态压缩dp（也称状压dp）。状压dp，顾名思义，就是把状态压缩起来。比如对于8*8 的棋盘，每个位置可以放一个棋子，对于在第i行第2个位置和第6个位置放了棋子，我们可能需要8维或9维数组表示。因此我们就有了把一行状态压缩成一个数字的做法。一般我们会转化为二进制，如果每个位置可以有3种状态，那我们可以采用三进制。这样只需要一个大小为2^8的一维数组我们就可以存下所有状态，这就是状态压缩。
[code]eg1• 现在有 n*m 的方格棋盘，和无限的 1*2 的骨牌，问有多少种方法能用骨牌 铺满棋盘。• 1