【动态规划5】状态压缩动态规划

对应进阶篇第 17 章。 在《基础篇》的“暴力枚举”一章中介绍了子集枚举，使用二进制数字来表示一种状态。对于“状态压缩动态规划”中的状态，通常与集合相关联。集合本身具有三个性质：确定性，互异性和无序性 。这也就决定了只关心每个元素的存在状态，而这通常可以使用 0 或者 1 表示存在 或者不存在。例如，一顿饭有 8 道菜，小明同学最终吃了某几道菜，必然是这 8 道菜的子集。令 1 表示吃了， 0 表示没吃，那么以下几个状态：10000001 表示只吃了 1 号菜和 8 号菜； 01010101 表示吃了 2 , 4 , 6 , 8 四道菜。 由此可见，可以通过一串 01 码来清晰地表示一个集合的状态。同时，在确定了最低位的前 提下，一串 0-1 码与一个二进制数一一对应。这种表示状态的方式被称为状态压缩，简称状压。所谓“压缩”，即是用一个二进制数来保存一组状态，将一个集合的状态压缩进了一个二进制数中，而通常这个二进制数在十进制下的大小可以作为其编号。状态压缩本质上是进行了两步操作： 1. 给这个集合的每个状态一个编号； 2. 通过该编号，轻易地访问该状态。 这一章将会从状态压缩谈起，描述一些简单的应用，并最终落脚到状态压缩应用最广泛的动态规划题目。