K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知经典01背包问题的二维动态规划状态定义为dp[i][j]表示从前i件物品中选择，放入容量为j的背包所能获得的最大价值，状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])。现在需要对该DP过程进行空间优化，以下选项描述正确的是？
dp[i][j]
i
j
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
优化后需使用二维数组，仅能减少代码行数无法减少空间占用
可将dp数组压缩为一维数组dp[j]，遍历背包容量时需从大到小倒序遍历
dp[j]
优化后的一维dp数组无法正确求解01背包问题，会丢失部分状态信息
空间优化仅能将二维数组压缩至二维，无法进一步降低空间复杂度