堆箱子问题：从暴力递归到动态规划的优化之路

堆箱子问题的核心是：在 “上层箱子宽、深、高必须严格小于下层” 的规则下，求可堆叠的最大高度和。这一问题的解法优化，是理解 “重复计算优化” 和动态规划思想的经典案例。

暴力递归是最基础的思路：通过枚举 “选 / 不选当前箱子” 的所有组合，递归求解最大值。但该方法存在大量重复计算，时间复杂度接近 O (2ⁿ)，仅适用于箱子数量 n≤20 的场景。

为解决重复计算问题，记忆化搜索应运而生。我们用数组记录 “以第 i 个箱子为堆顶的最大高度”，递归时先查询记忆数组，已计算的结果直接复用，无需重复递归，将时间复杂度降至 O (n²)，大幅提升效率。

进一步优化可转为动态规划的迭代实现：定义 dp [i] 为 “以第 i 个箱子为堆顶的最大高度”，先按宽 / 深 / 高降序排序箱子（简化堆叠条件判断），再通过两层循环递推 —— 初始化 dp [i] 为当前箱子高度，遍历前面所有可堆叠的箱子 j，用 dp [j]+ 当前高度更新 dp [i]，最终取 dp 数组最大值即为答案。