什么是状压

  • 对于题目中一种复杂的状态，如多维，多行，多条路，某种方案，某种集合等压缩成一个整数的过程就是状态压缩
  • 这也可以看作是一个Hash的过程
  • 除去压缩状态的过程，其实它整体和普通的dp差别不大，都是从已知过程推向位置过程
  • 压缩的意义在于把一个一般无法描述的状态，变成一个包含多种信息的状态，而这个状态又可以用二进制数(三进制，四进制也有可能)表示

什么时候考虑状压dp

  • 棋盘格覆盖
  • 类似TSP的路径问题
  • N比较小(20左右)，且变成N位二进制比较合理