1. 问题背景与题目解析今天我们来拆解一道经典的动态规划问题——LeetCode 1105题填充书架。这道题在2023年频繁出现在各大科技公司的面试中特别是Amazon和Google的算法轮次。题目看似简单但隐藏着几个容易踩坑的细节。题目描述是这样的你有一个书架宽度为shelf_width。现在给你一系列书籍每本书用一个二元组表示[厚度, 高度]。你需要将这些书按顺序摆放到书架上当一行书的厚度总和不超过shelf_width时可以放在同一层。书架的总高度是各层最大高度之和。要求找出摆放这些书的最小总高度。举个例子 输入books [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width 4 输出6 解释 第一层[1,1], [2,3], [1,1] (总厚度4最大高度3) 第二层[1,1], [1,2] (总厚度3最大高度2) 第三层[1,1] (总厚度1最大高度1) 总高度32162. 解题思路与动态规划分析2.1 暴力递归思路最直观的解法是考虑所有可能的摆放组合。对于每本书我们有两种选择放在当前层如果厚度允许新开一层放置这种思路可以用递归实现但时间复杂度会达到O(2^n)显然不适用于大规模数据。2.2 动态规划优化我们定义dp[i]表示摆放前i本书的最小总高度。状态转移方程需要考虑从当前书开始回溯尽可能多地将连续的书放在同一层dp[i] min(dp[j] max_height(j1,i)) for all j where sum_width(j1,i) shelf_width其中max_height(j1,i)表示第j1到第i本书的最大高度sum_width(j1,i)表示这些书的总厚度。2.3 关键实现细节在实际编码时有几个关键点需要注意初始条件dp[0] 0没有书时高度为0每层书的厚度总和不能超过shelf_width需要在内层循环中维护当前层的最大高度和总厚度时间复杂度优化由于每本书最多被处理一次最终时间复杂度为O(n^2)3. 代码实现与逐行解析以下是Python的完整实现带有详细注释def minHeightShelves(books, shelf_width): n len(books) dp [float(inf)] * (n 1) dp[0] 0 # 初始条件0本书高度为0 for i in range(1, n 1): max_h 0 current_w 0 # 从第i本书向前回溯尽可能多地放在同一层 for j in range(i, 0, -1): current_w books[j-1][0] # 累加厚度 if current_w shelf_width: break max_h max(max_h, books[j-1][1]) # 更新当前层最大高度 dp[i] min(dp[i], dp[j-1] max_h) return dp[n]代码解析初始化dp数组长度为n1初始值为无穷大设置dp[0]0作为基准情况外层循环遍历每本书内层循环从当前书向前回溯计算可能的摆放组合当累计厚度超过shelf_width时终止内层循环动态更新当前层的最大高度和最小总高度4. 复杂度分析与优化空间4.1 时间复杂度该算法的时间复杂度主要取决于双重循环外层循环执行n次内层循环在最坏情况下也执行n次 因此总时间复杂度为O(n^2)4.2 空间复杂度我们只需要维护一个长度为n1的dp数组因此空间复杂度为O(n)4.3 可能的优化方向虽然O(n^2)已经是不错的解法但在某些特殊情况下还可以优化当shelf_width特别大时可以尝试贪心算法使用单调栈来优化内层循环的查找过程对于特定分布的数据如高度单调递增可以提前终止内层循环5. 常见错误与调试技巧5.1 典型错误案例很多同学在实现时会犯以下错误忘记处理初始条件dp[0]0在内层循环中错误地更新max_h应该在每次外层循环开始时重置错误地计算书本索引注意books是0-based而dp是1-based没有及时break导致厚度超限5.2 调试建议当你的代码不能通过测试用例时先打印出dp数组的中间结果对于小规模测试用例手动计算预期结果检查内层循环中max_h和current_w的更新逻辑特别注意边界条件如只有一本书或shelf_width很小的情况6. 相似题目与扩展思考6.1 LeetCode相似题目这道题与以下几个题目有相似之处最长递增子序列LIS俄罗斯套娃信封问题灌溉花园的最少水龙头数目分隔数组以得到最大和6.2 实际问题扩展这个问题在实际应用中有多种变体仓库货架摆放优化网页内容分页算法集装箱装载问题内存分页管理6.3 进阶挑战如果你已经掌握了基础解法可以尝试以下挑战如果允许调整书的顺序如何求解如果书架有高度限制如何判断是否能够放下所有书如果每层的高度不是最大值而是平均值如何修改算法7. 个人刷题心得在解决这类动态规划问题时我总结了几个关键步骤明确dp数组的定义在这题中是前i本书的最小高度找出状态转移方程如何用子问题的解构建当前解确定初始条件和边界情况考虑计算顺序这题是从左到右思考可能的优化空间对于这道题特别要注意的是内层循环的方向——从当前书向前回溯而不是从前往后。这是因为我们需要考虑将连续的多本书放在同一层这个约束条件。在实际面试中建议先写出暴力解法再逐步优化并向面试官解释你的思考过程。 
长河君 · 2026/10/28 18:06:57 · 阅读 1.2k 动态规划解决LeetCode 1105填充书架问题
1. 问题背景与题目解析今天我们来拆解一道经典的动态规划问题——LeetCode 1105题填充书架。这道题在2023年频繁出现在各大科技公司的面试中特别是Amazon和Google的算法轮次。题目看似简单但隐藏着几个容易踩坑的细节。题目描述是这样的你有一个书架宽度为shelf_width。现在给你一系列书籍每本书用一个二元组表示[厚度, 高度]。你需要将这些书按顺序摆放到书架上当一行书的厚度总和不超过shelf_width时可以放在同一层。书架的总高度是各层最大高度之和。要求找出摆放这些书的最小总高度。举个例子 输入books [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width 4 输出6 解释 第一层[1,1], [2,3], [1,1] (总厚度4最大高度3) 第二层[1,1], [1,2] (总厚度3最大高度2) 第三层[1,1] (总厚度1最大高度1) 总高度32162. 解题思路与动态规划分析2.1 暴力递归思路最直观的解法是考虑所有可能的摆放组合。对于每本书我们有两种选择放在当前层如果厚度允许新开一层放置这种思路可以用递归实现但时间复杂度会达到O(2^n)显然不适用于大规模数据。2.2 动态规划优化我们定义dp[i]表示摆放前i本书的最小总高度。状态转移方程需要考虑从当前书开始回溯尽可能多地将连续的书放在同一层dp[i] min(dp[j] max_height(j1,i)) for all j where sum_width(j1,i) shelf_width其中max_height(j1,i)表示第j1到第i本书的最大高度sum_width(j1,i)表示这些书的总厚度。2.3 关键实现细节在实际编码时有几个关键点需要注意初始条件dp[0] 0没有书时高度为0每层书的厚度总和不能超过shelf_width需要在内层循环中维护当前层的最大高度和总厚度时间复杂度优化由于每本书最多被处理一次最终时间复杂度为O(n^2)3. 代码实现与逐行解析以下是Python的完整实现带有详细注释def minHeightShelves(books, shelf_width): n len(books) dp [float(inf)] * (n 1) dp[0] 0 # 初始条件0本书高度为0 for i in range(1, n 1): max_h 0 current_w 0 # 从第i本书向前回溯尽可能多地放在同一层 for j in range(i, 0, -1): current_w books[j-1][0] # 累加厚度 if current_w shelf_width: break max_h max(max_h, books[j-1][1]) # 更新当前层最大高度 dp[i] min(dp[i], dp[j-1] max_h) return dp[n]代码解析初始化dp数组长度为n1初始值为无穷大设置dp[0]0作为基准情况外层循环遍历每本书内层循环从当前书向前回溯计算可能的摆放组合当累计厚度超过shelf_width时终止内层循环动态更新当前层的最大高度和最小总高度4. 复杂度分析与优化空间4.1 时间复杂度该算法的时间复杂度主要取决于双重循环外层循环执行n次内层循环在最坏情况下也执行n次 因此总时间复杂度为O(n^2)4.2 空间复杂度我们只需要维护一个长度为n1的dp数组因此空间复杂度为O(n)4.3 可能的优化方向虽然O(n^2)已经是不错的解法但在某些特殊情况下还可以优化当shelf_width特别大时可以尝试贪心算法使用单调栈来优化内层循环的查找过程对于特定分布的数据如高度单调递增可以提前终止内层循环5. 常见错误与调试技巧5.1 典型错误案例很多同学在实现时会犯以下错误忘记处理初始条件dp[0]0在内层循环中错误地更新max_h应该在每次外层循环开始时重置错误地计算书本索引注意books是0-based而dp是1-based没有及时break导致厚度超限5.2 调试建议当你的代码不能通过测试用例时先打印出dp数组的中间结果对于小规模测试用例手动计算预期结果检查内层循环中max_h和current_w的更新逻辑特别注意边界条件如只有一本书或shelf_width很小的情况6. 相似题目与扩展思考6.1 LeetCode相似题目这道题与以下几个题目有相似之处最长递增子序列LIS俄罗斯套娃信封问题灌溉花园的最少水龙头数目分隔数组以得到最大和6.2 实际问题扩展这个问题在实际应用中有多种变体仓库货架摆放优化网页内容分页算法集装箱装载问题内存分页管理6.3 进阶挑战如果你已经掌握了基础解法可以尝试以下挑战如果允许调整书的顺序如何求解如果书架有高度限制如何判断是否能够放下所有书如果每层的高度不是最大值而是平均值如何修改算法7. 个人刷题心得在解决这类动态规划问题时我总结了几个关键步骤明确dp数组的定义在这题中是前i本书的最小高度找出状态转移方程如何用子问题的解构建当前解确定初始条件和边界情况考虑计算顺序这题是从左到右思考可能的优化空间对于这道题特别要注意的是内层循环的方向——从当前书向前回溯而不是从前往后。这是因为我们需要考虑将连续的多本书放在同一层这个约束条件。在实际面试中建议先写出暴力解法再逐步优化并向面试官解释你的思考过程。