第4-4课：状态压缩与动态规划
source link: https://blog.csdn.net/orbit/article/details/108729358
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
什么是状态压缩
动态规划问题中重要的一环就是确定状态的定义，在大多数情况下，状态中所包含的信息并不多，比如线性规划问题的状态一般表示为 d[i，j]（i 表示状态的位置，j 表示状态的阶段），算法实现时可用二维数组保存计算过程中的状态。但是也有一些问题，它的状态中包含的信息很多，比如它的状态可能是一个集合中各个元素的情况，或者是像铺瓷砖问题这样，是某一行的覆盖状态。如果沿用简单的状态表示方法，则可能会用到 N 维数组，这样不仅空间占用大，而且状态的转移（状态递推公式）算法也会非常复杂。不信？读者猜猜这个状态 d[i, j, k, l, m, n, o, p, q, r, s, t] 的下一个状态是什么，是 t + 1 还是 q + 1 ?
在这种情况下，如果我们能用一种编码策略，将前面例子中的 j, k, l, m, n, o, p, q, r, s, t 编码成一个整数数字，就可以将状态简化成 d[i, encode(j, k, l, m, n, o, p, q, r, s, t)]，这种情况下就可以用二维数组来保存状态，并且状态的递推公式也会简单很多。这种策略看起来好像状态被“压缩”了，所以被称为状态压缩动态规划。
状态压缩和动态规划
严格来说，状态压缩是状态压缩，动态规划是动态规划，是算法模式，它们只是碰巧一起发生了而已。这种通过某种编码和解码方式将某些离散的信息（比如集合中各个元素的状态）转化成某种简单数值类型进行计算和处理的方法，在很多算法中都有体现，并非状态规划独有的方法。最常见的就是各种 hash 算法，通过比较 hash 值的方法比较原始数据的差异要比直接比较原始数据简单高效。
<Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK