状态压缩动态规划

例：蒙德里安的梦想

例题：蒙德里安的梦想

摆放方块的时候，先放横着的，再放竖着的。总方案数等于只放横着的小方块的合法方案数。

如何判断当前方案数是否合法？应该看所有剩余位置能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。

例：最短哈密顿路径

例题：最短Hamilton路径

动态规划的表示：

• 状态表示：
  • 集合： \(f(i,j)\) 表示所有从 \(0\) 开始走到 \(j\)，走过的所有点存在 \(i\) 的二进制表示当中的路径 ( \(i\) 是所有经过点的集合，用二进制表示， \(1\) 位表示走过了， \(0\) 位表示没走过)；
  • 属性：路径长度的最小值。
• 状态计算：用倒数第二个点是哪个点来分类。

设倒数第二个点为 \(k\)，则：

\[ f\left( i,j \right) =\min_k \left[ f\left( i,j \right) , f\left( i-\mathrm{point}\ \mathrm{j},k \right) +a\left( k,j \right) \right] \]