第28279题 单选题
在C++中优化01背包问题的动态规划解法，将空间复杂度从O(nV)降至O(V)的正确实现是？

常规01背包的二维动态规划数组定义为dp[i][j]，表示前i件物品放入容量为j的背包可获得的最大价值，其空间复杂度为O(nV)。若要将空间复杂度优化至O(V)，以下哪种实现方式是正确的？

A

继续使用二维DP数组，仅缩小数组的存储空间

B

将DP数组改为一维数组dp[j]，遍历物品时正序遍历背包容量j

C

将DP数组改为一维数组dp[j]，遍历物品时逆序遍历背包容量j

D

直接舍弃所有中间状态，仅保留最终的计算结果

程序运行统计
暂无判题统计
知识点：
C++-动态规划空间优化
提交0次 正确率0.00%
答案解析
上一题 下一题