针对经典01背包问题的动态规划空间优化,下列说法正确的是?

ee912524 单选题 共 个子题

已知经典01背包问题的二维动态规划状态定义为dp[i][j]表示从前i件物品中选择,放入容量为j的背包所能获得的最大价值,状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])。现在需要对该DP过程进行空间优化,以下选项描述正确的是?

A

优化后需使用二维数组,仅能减少代码行数无法减少空间占用

B

可将dp数组压缩为一维数组dp[j],遍历背包容量时需从大到小倒序遍历

C

优化后的一维dp数组无法正确求解01背包问题,会丢失部分状态信息

D

空间优化仅能将二维数组压缩至二维,无法进一步降低空间复杂度

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧