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)。

代码如下:

全部评论

相关推荐

05-09 13:22
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务