动态规划状态压缩:从 O(2^N) 到 O(N) 的空间优化方法论
动态规划状态压缩:从 O(2^N) 到 O(N) 的空间优化方法论一、空间爆炸——动态规划的隐性瓶颈动态规划的时间复杂度通常由状态总数和单状态转移代价的乘积决定,这已是共识。但一个常被忽视的事实是:空间复杂度同样可能成为瓶颈,而且在实际工程中,空间瓶颈往往比时间瓶颈更致命——时间超限可以通过重试或并行缓解,空间超限

