01背包优化空间复杂度

01背包的时间复杂度很难再降低了，但空间复杂度还能进行优化，我们可以把数组从二维降到一维。

两重循环，空间复杂度为O(nv)。

下面我们把空间复杂度降为O(v)：

当计算第i件物品时，需要的状态为dp[i-1][0~v],i和i-1存储在不同的地方。

如果我们从大到小遍历，即从v-0，我们仍只需知道第i-1物品的状态。

因此我们可以优化转移方程为dp[j]=max(dp[j−w[i]]+v[i],dp[j])将复杂度降为O(v)。

代码如下：