状压DP 详解教程 简单易学(bushi

状压DP补档

一、基本概念

• 什么是状压DP
  

状态压缩动态规划（State Compression Dynamic Programming）是一种通过二进制或其他紧凑表示方式来优化状态空间的动态规划方法。它通常用于解决状态可以表示为集合或排列的问题。

• 适用场景
  状态可以表示为集合（如选/不选某些元素）
  

状态维度较高但每个维度状态较少（如棋盘覆盖问题）
需要记录访问历史或选择历史的问题

• 核心思想
  用二进制数表示状态（0/1表示存在/不存在）
  

通过位运算高效地进行状态转移
将指数级的状态空间压缩为多项式级
二、常用位运算技巧

• 基本操作
  

[code]// 设置第i位为1mask |= (1