北京医院治皮炎 http://m.39.net/news/a_9052771.html前面我们讲了01背包问题，下面来介绍通过滚动数组和内循环逆序来优化我们的答案
滚动数组是一种能够在动态规划中降低空间复杂度的方法，有时某些二维dp方程可以直接降阶到一维，在某些题目中甚至可以降低时间复杂度，是一种极为巧妙的思想
好吧，其实也没有特别巧妙，实质上就是：
因为当前的数据是只有前面的一个数据导出来的，所以前面的数据如果不需要，我们就可以把它覆盖掉，以此来达到减少存储空间，减少空间复杂度的效果；从整个过程上去看，这个数组是滚动的，所以称为滚动数组
以01背包问题为例
二维dp方程dp[j]=max(dp[i-1][j],dp[i-1][j-weight]+value)
我们可以清楚的看出来，dp方程递归过程是不断地由上一行的数据传递到下一行，也就是说当我们递推到dp[j]时，对于那些只要求最终最佳答案的题目来说，只需要i-1这行的数据即可，至于上面的i-2,i-都是不需要的数据
所以对于求一维数组dp,我们在用dp[i-1]求出之后，用dp去覆盖dp[i-1],然后再去计算dp[i+1]
这样经过滚动数组优化后的01背包只用两个数组
更新后的状态转移方程为：
for(inti=1;i=n;i++)
for(intj=v;j=weight;j--)//倒序保证数据更新的有序性，保证只取一次，正序则是完全背包的写法
dp[j]=max(dp[j],dp[j-weight]+value);
为什么第二维的数组是倒序递推（内循环逆序）？
观察代码，我们可以发现在优化之后我们不再使用dp[j-1]，而是使用dp[j]，在未优化之前我们可以保证每一次状态转移用的都是上一次的结果，但是优化之后，因为“j-weight”这个尝试，要求我们必须此时使用的结果必须是上一次的结果，而顺序遍历的话会导致此时使用的“上一次的结果”已经被前面运算得到的结果所覆盖了，所以如果要保证每一次运算都是上一次的结果就必须逆序
红色域是我们已经更新过的部分，红色方块是正在调用的数据，绿色方块是我们正在计算的，可以发现如果正序，我们调用的数据都是前面的被更新过的数据
很直观的，我们采用逆序，会发现被调用的数据（红色方块）并不在红色域内，也就是说被调用的数据并没有被更新过而是上一次保留下来的数据，这正是我们所期望的
代码对比：
优化后空间复杂度由O(NV)降低为O(V)
