原创动态规划核心框架约 2844 字大约 9 分钟
Info
新版网站会员 即将涨价;已支持老用户续费~
写在最前面
空间压缩并不难,可以理解为一种投机取巧的办法去优化某些动态规划问题的空间复杂度。我个人认为状态压缩并不是必须掌握的技巧,如果你对这个技巧感兴趣,需要先阅读并理解 动态规划系列答疑篇。
我们号之前写过十几篇动态规划文章,可以说动态规划技巧对于算法效率的提升非常可观,一般来说都能把指数级和阶乘级时间复杂度的算法优化成 O(N^2),堪称算法界的二向箔,把各路魑魅魍魉统统打成二次元。
但是,动态规划求解的过程中也是可以进行阶段性优化的,如果你认真观察某些动态规划问题的状态转移方程,就能够把它们解法的空间复杂度进一步降低,由 O(N^2) 降低到 O(N)。