第28283题 单选题
针对01背包问题的动态规划空间优化,下列说法与代码实现正确的是?

已知常规01背包问题的二维动态规划解法核心代码如下:

// 常规二维DP解法
int dp[1005][1005] = {0};
// weight数组存储物品重量,value数组存储物品价值,n为物品总数,V为背包总容量
for(int i = 1; i <= n; i++){
    for(int j = 0; j <= V; j++){
        if(j < weight[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);
    }
}

若对该解法进行空间优化,以下说法与实现正确的是?

A

空间复杂度仍为$O(nV)$,优化后的代码需将dp数组改为一维,且遍历背包容量时从大到小枚举

B

空间复杂度优化为$O(V)$,优化后的代码需将dp数组改为一维,且遍历背包容量时从小到大枚举

C

空间复杂度优化为$O(V)$,优化后的代码需将dp数组改为一维,且遍历背包容量时从大到小枚举

D

空间复杂度优化为$O(n)$,优化后的代码仅需保留前一个物品的DP状态数组,遍历背包容量时无特殊顺序要求

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析