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)。
代码如下：
2019-08-09 22:29 已编辑 第一拖拉机制造厂拖拉机学院 信息技术岗
关注
全部评论
相关推荐
查看5道真题和解析
11-11 15:12
南昌大学 材料工程师 
一个菜鸡罢了：哥们，感觉你的简历还是有点问题的，我提几点建议，看看能不能提供一点帮助
1. ”新余学院“别加粗，课程不清楚是否有必要写，感觉版面不如拿来写一下做过的事情，教育经历是你的弱势就尽量少写
2. “干部及社团经历”和“自我评价”删掉
3. 论文后面的“录用”和“小修”啥的都删掉，默认全录用，问了再说，反正小修毕业前肯定能发出来
4. 工作经验和研究成果没有体现你的个人贡献，着重包装一下个人贡献 点赞 评论 收藏
分享