DP算法中，如何实现滚动数组来优化空间复杂度？

本文共计373个文字，预计阅读时间需要2分钟。

滚动数组是一种利用时间换空间的优化思想。简单来说，就是每次都使用固定的几个存储空间，达到压缩节点的效果，主要用于递推或动态规划中（如背包问题）。

滚动数组

滚动数组是用时间换空间的一种优化思想。简单的理解就是每次都使用固定的几个存储空间达到压缩节省存储空间的作用，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。