对动态规划进行空间压缩

动态规划算法的主要表现形式是带备忘录的递归解法，或者递推的迭代解法，这两种解法本质上都是一样的，效率也差不多。

本文将介绍动态规划迭代写法的一个优势，就是可以将 dp 数组进行空间压缩（一般称为滚动数组技巧），降低空间复杂度。

简单说就是，某些情况下状态转移方程仅依赖于相邻的状态，那么就没必要维护整个 dp 数组，仅维护所需的几个状态即可，这样可以降低空间复杂度。

我个人认为空间压缩技巧不是必须掌握的，原因是：

1、一般的笔试中对空间的要求并不高，大部分情况下，即便不使用这个优化技巧也能通过所有测试用例。

2、使用空间压缩技巧之后代码可读性会变得非常差，不利于理解和调试。

所以本文作为选学内容，有兴趣的读者可以仔细学习理解一下。