K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知使用二维动态规划数组解决01背包问题的状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])，其中dp[i][j]表示前i件物品放入容量为j的背包的最大价值，总物品数为n，背包最大容量为m。
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
dp[i][j]
无法进行空间优化，必须使用二维dp数组，空间复杂度为O(nm)
可以优化为一维dp数组，内层循环采用顺序遍历背包容量即可
可以优化为一维dp数组dp[j]，且内层循环需要逆序遍历背包容量，优化后空间复杂度为O(m)
dp[j]
优化后空间复杂度从O(nm)降低至O(n)，仅与物品数量相关