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] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
优化后的一维DP数组可以从左到右（从小到大）遍历背包容量j进行状态更新
优化后的空间复杂度从O(nm)降低至O(n)，其中n为物品数量，m为背包容量
空间优化的核心是当前状态仅依赖于上一轮（i-1）的DP状态，可通过复用数组空间实现
优化后无需再保存每件物品的重量weight和价值value数组