状态压缩动态规划(状压DP)详解

0 引子
在计算机里，整数是以二进制的方式存储的。把状态信息压缩成二进制当成状态进行动态规划，就是状压DP的基本思想。
是不是一脸懵比？别急着关掉文章，接着往下看，你会发现一个新世界。
0.5 状压能解决什么样的问题？
让我们康康这道题：传送门
很容易想到搜索，不是吗？
然而，我们要用更装比 复杂 优美的方式完成这道题。
1.什么是“状态压缩？”
举个例子吧。例如，例题里的“取哪些砝码”这个信息，就可以压缩进一个int整数里。因为，int整数是二进制存储的。大概长这样：

/[/]

十进制二进制(也就是计算机里实际的状态)11210114514110111111010100106110
我们可以发现，数字是由许多二进制位构成的，要么是0要么是1。
是不是发现了什么？
没错，我们可以用每一位的0和1表示每一个砝码选或者不选！
例如，数字 2 (二进制：10) 就可以表示1号砝码不选，2号砝码选的状态。(因为第1位是0，第2位是1)。
知道了如何压缩，就可以用动态规划的方式求解

状态压缩动态规划(状压DP)详解最先出现在Python成神之路。