对动态规划进行降维打击
原创约 2369 字
写在最前面
空间压缩并不难，主要用来优化某些动态规划问题的空间复杂度。但是一般的笔试中对空间的要求并不高，即便不使用这个优化技巧也能通过，所以我个人认为状态压缩并不是必须掌握的技巧，有兴趣的读者可以仔细学习理解一下。
我们号之前写过十几篇动态规划文章，可以说动态规划技巧对于算法效率的提升非常可观，一般来说都能把指数级和阶乘级时间复杂度的算法优化成 O(N^2)，堪称算法界的二向箔，把各路魑魅魍魉统统打成二次元。
但是，动态规划求解的过程中也是可以进行阶段性优化的，如果你认真观察某些动态规划问题的状态转移方程，就能够把它们解法的空间复杂度进一步降低，由 O(N^2) 降低到 O(N)。