Pythonist

01 背包问题详解与空间优化实战

01 背包是动态规划的经典入门题，核心在于决策每个物品选或不选。详细解析了两种常见变体：求最大价值与恰好装满背包的最大价值。通过二维 DP 推导状态转移方程，并进一步讲解如何利用滚动数组将空间复杂度从 O(nV) 降至 O(V)。重点说明了逆序遍历的必要性及初始化细节（如用 -1 标记不可达状态），附带完整 C++ 代码示例，适合算法初学者巩固基础。