概念 数组是最常见的数据结构之一,现在对数组的下标进行特殊处理,使每一次操作仅保存有用信息,新的元素不断循环更新,看上去数组的空间被滚动的利用,此模型成为滚动数组。其主要目的是压缩存储,一般在动态规划问题中使用。 例题 一、0-1背包问题 n和物品x1,x2,...,xn的价值和重量分别为: v1,v2,...,vn w1,w2,...,wn现有一个背包,其最大载重量为m,求如何装包是所装物品的价值和最大? 构造二维动态数组 构造:构造dp[n][m]数组,从n个物品中选择,装到m容量的包中的最大价值和。 base case:dp[0][j] = 0dp[i][0] ...