动态规划算法博大精深，非常的广泛而复杂。但动态规划离不开状态的存储和转移，要想用动态规划来求解一个问题，必须把问题分解为多个子问题，然后再用状态来记录以解决子问题，最终通过状态转移以得到整个问题的解。根据问题的不同，状态也会有不同的定义，比如有些是用整数来代表计数，有些是用布尔来代表True/False（或者0/1）的状态。
如果状态可以用True/False（或者0/1）来代表时，那么可以进一步的利用位运算，利用计算机的bit的特点，一个bit可以是0也可以是1，足以表示一个状态，那么就可以把整体的状态只用一个或者几个有限的整数来表示了，这就是状态压缩。
更进一步的，其实可以拓展一下，不光局限在动态规划里面，凡是用到True/False（或者0/1，选与不选等）的辅助存储时，都可以尝试用位运算来代表数组或者哈希表，这其实也是状态压缩。广义上来讲，把一坨用数组或者哈希表表示的状态压缩成为一个整数或者几个有限的整数就是状态压缩。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 318. 最大单词长度乘积 | 题解 | |
| 题解 | ||
| 题解 |
参考资料
- 状态压缩：对动态规划进行降维打击
- Bitmask DP
- 动态规划之状态压缩DP详细介绍和例题练习
- OI wiki 状压DP
- 【状压DP】状态压缩动态规划入门超详解
- 动态规划——状态压缩DP
- 状态压缩入门
- Bitmask Dynamic Programming
- Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person)
- Bitmasking and Dynamic Programming | Set-2 (TSP)
- Bitmask and Dynamic Programming