滚动数组

  • 滚动数组是基于二维数组之上产生的，之所以滚动数组能够用一维的方式去完成和二维同样的工作，原因就是在于这个滚动数组能够重复产生数据，进而有“滚动”的效果。
  • 滚动数组的本质还是二维数组，只是数据不再产生新的行，只在一行上一直进行数据的覆盖更新，因此要特别注意数据污染的情况。
📌
下面就数据污染问题，以01背包做出解释
看下面一段01背包遍历代码
从代码中，我们可以看出，由于背包容量j是从小到大遍历的，那么就会导致存在一种可能：容量较小的背包A，放了某一物体a，后面容量较大的背包B，再利用了前面的背包A，同时又放入了物体a，这就违背了01背包的前提条件。图示如下：
notion image
因此，为了避免滚动数组造成的数据污染问题，要逆序遍历背包容量j。