第28288题 单选题
针对01背包问题的动态规划空间优化,下列哪个一维DP实现是正确的?

已知01背包问题的二维动态规划标准解法如下,其中n为物品总数,V为背包最大承重,w数组存储每件物品的重量,v数组存储每件物品的价值:

int dp[105][1005] = {0};
for(int i = 1; i <= n; i++){
    for(int j = 0; j <= V; j++){
        dp[i][j] = dp[i-1][j];
        if(j >= w[i]) dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
    }
}

现需对该解法进行空间优化,将二维DP数组压缩为一维数组,下列实现正确的是?

{{ option.label }}
子题{{ index + 1 }} {{ child.type_label }}
{{ option.label }}
✓ 正确 ◐ 部分正确 ✗ 错误
程序运行统计
暂无判题统计
提交{{ questionInfo.stats ? questionInfo.stats.submit_count : 0 }}次 正确率{{ statsAccuracy }}%
答案解析