如果说到动态规划，大概我那个年代的人第一时间想到的永远是背包问题，而大部分人在面试中考试中遇到最多的背包问题，可能就是01背包和完全背包了。这一段，我们从01背包开始，慢慢记录我关于背包类dp问题的学习历程。
首先，来看一下道最常见的题目：
我们现在有一个可装载重量为W的背包，眼前有N个物品，每个物品的重量为wi，对应的价值为vi，问现在用这个背包，我们能装最多价值为多少的商品。
这个问题，相信如果熟悉动态规划的人，应该可以很轻松的得到递推方程
代表当前第i个物品背包空间还剩下j时所装在的商品价值，只有两个状态，一个是不拿取当前的物品，一个是拿取当前的物品，并加上价值，对比这两个状态就可以得到当前的状态了。
01背包是最基础的背包问题，它只涉及两个很简单的状态，只需要判断拿或者不拿，在一个二重循环里判断就可以了。
for(int i = 0 ; i < n; i ++){
for(int j = 0 ; j < w ; j ++){
dp[i][j] = dp[i-1][j];
dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}在01背包的问题里，先遍历物品还是先遍历空间这个问题并不是很明显，因为在01背包中，当前的状态dpij所需要的状态来源于左上角和正上方，无论哪种遍历方式都不会影响到我们后续的判断，因为左上角和正上方的数据不会被覆盖或者影响。但是在其他的背包问题中，我们需要根据状态方程仔细考虑这两重循环的顺序，这也是背包问题的难点之一。
但是可以看到，在上述的递推式中其实只用到了i和i-1这两行dp状态，所以很显然的我们可以通过两个数组来循环表示i和i-1这两行状态，这就是所谓的滚动数组。但是通过观察递推式，我们看到当前dpij这个状态，其实是从上一行的正上方和左上方得来的，那么我们只需要保证在计算dpij之前没有计算dpi(j-wi)我们就可以得到一个一维数组的优化。需要注意的是，这里的第二层循环遍历顺序是不能变的，否则就会在修改dpij之前将j前面保存的上一行的状态覆盖成当前行的状态了。
for(int i = 0 ; i < n ; i ++){
for(int j = w ; j > w[i] ; j --){
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}