1. 问题引入从“积木塔”到“最优解”的思考最近在整理蓝桥杯的历年真题时翻到了第十四届省赛Python组的一道题目编号是17822标题叫“乐乐的积木塔”。说实话第一眼看到这个标题我脑子里浮现的是小时候玩积木的场景但题目描述一出来就知道这完全不是搭着玩的游戏而是一个典型的、带有约束条件的最优化问题。这类问题在算法竞赛和实际开发中都非常常见比如资源分配、任务调度、背包问题等等核心思想都是在给定的规则下找到那个“最好”的方案。这道题的具体场景是这样的乐乐有一堆高度不同的积木他想要用它们搭建一座塔。但搭建有规则每次只能将一块积木放在另一块积木的顶部并且要求顶部积木的边长必须严格小于底部积木的边长。我们的目标是用给定的这堆积木计算出能够搭建出的最高塔的高度。这听起来是不是有点像我们熟悉的“最长上升子序列”问题但仔细一想又有区别。最长上升子序列通常是在一个序列里找顺序是固定的。而这里我们面对的是一堆无序的积木我们可以自由选择先用哪块、后用哪块只要满足“上小下大”的塔形规则即可。这给了我们很大的操作空间也增加了问题的复杂度——我们不能再简单地扫描一遍序列就得到答案。在开始动手写代码之前我习惯先抛开电脑用纸笔模拟几个小例子。比如假设我们有四块积木高度和边长分别是[(10, 5), (20, 8), (15, 3), (25, 12)]这里用(高度, 边长)表示。如果我们盲目地尝试可能会发现多种搭法但如何系统地找到最高的那个呢这个问题让我思考了很久也试错了好几种思路。今天我就把从理解题意、到思路演进、再到最终代码实现和优化的完整过程以及其中踩过的坑详细地分享出来。无论你是正在备赛蓝桥杯还是对动态规划感兴趣相信这篇“踩坑实录”都能给你带来一些启发。2. 核心思路剖析为什么动态规划是正解面对“乐乐的积木塔”这个问题我们首先要拒绝直觉上的贪婪想法。比如是不是每次都选当前还能放上去的、高度最高的积木就能得到最高的塔我们用一个简单的反例就能推翻它。假设有三块积木A(高100, 边长50) B(高80, 边长45) C(高90, 边长55)。如果按照“贪高度”的策略我们会先选A高100作为塔基。那么接下来能放在A上面的积木边长必须小于50。B的边长是45符合可以放上去此时塔高为180。C的边长是55大于50无法放置。最终塔高是180。但如果换一种思路我们选择C(高90, 边长55)作为塔基那么A(边长5055)和B(边长4555)都可以放在它上面我们可以先放A高100再放B高80塔高为9010080270。显然270远大于180。这个例子清晰地告诉我们局部的最优选择单块积木高度最高无法保证全局结果最优。塔的高度是所有使用积木的高度之和而能否放置一块积木只取决于它的边长与它下面那块积木边长的相对大小关系。一个边长更大的积木作为塔基可能为更多的高度可观的积木提供“入场券”。既然贪心不行我们就要考虑更系统的方法。一个自然的想法是搜索比如深度优先搜索(DFS)枚举所有可能的积木排列顺序。对于n块积木理论上有n!种排列但其中绝大部分会因为不满足边长约束而被剪枝。即便如此当n较大时比如n20搜索空间依然会爆炸导致程序超时。竞赛题目的数据规模通常会卡掉指数级复杂度的算法。那么如何高效解决呢这就要引入我们今天的主角——动态规划。动态规划的核心思想是“将大问题分解为小问题并存储小问题的解以避免重复计算”。对于本题一个关键的突破口是排序。注意动态规划的状态设计和转移方程是解题的灵魂直接决定了算法的效率和正确性。我们仔细审视规则“顶部积木的边长必须严格小于底部积木的边长”。这意味着如果我们把积木按照某个维度排序可能会让问题变得更清晰。应该按什么排序呢高度还是边长让我们来分析一下。如果我们按高度排序似乎没什么帮助因为放置规则只关心边长。如果我们按边长排序呢假设我们将所有积木按照边长从大到小排序。那么对于排序后的序列当我们考虑第i块积木时它有可能被放在所有排在它前面的积木即边长大于等于它的积木之上但前提是满足“严格小于”的规则。这依然是一个复杂的后效性问题。这里需要一点巧思。我们定义动态规划的状态dp[i]表示以第i块积木作为塔顶时所能形成的最大塔高。注意这里是“作为塔顶”而不是“作为塔基”。这个定义的好处在于它天然地处理了“顶部”这个概念。那么状态如何转移呢要计算dp[i]我们需要考虑所有可能放在第i块积木下面的积木j。积木j需要满足两个条件j的边长必须大于i的边长这样i才能放在j上面。在所有满足条件1的j中我们选择那个能使得“以j为顶的塔”最高的一个然后加上i本身的高度。因此转移方程可以写为dp[i] height[i] max{ dp[j] }其中j满足side[j] side[i]且0 j i。这里有一个细节j的范围是0到i-1吗这取决于我们如何安排计算顺序。如果我们按照任意顺序遍历积木那么对于每块积木i我们都需要检查所有其他的积木j这会导致O(n²)的复杂度在n较大时比如n1000是完全可以接受的100万次操作这也是本题最直接的解法。但是我们还可以进一步优化。如果我们先将所有积木按照边长从大到小排序那么对于排序后的数组当我们计算dp[i]时所有边长大于side[i]的积木都已经在i之前被处理过了即它们的dp值已经计算好了。这样我们只需要遍历i之前的所有积木找到边长严格大于side[i]且dp值最大的那个j即可。虽然复杂度仍是O(n²)但代码逻辑更清晰并且为后续可能的优化如数据结构优化奠定了基础。然而这里有一个陷阱边长相同的积木如何处理题目要求“严格小于”。如果两块积木边长相同那么它们互相都不能放在对方的上面。在我们排序后边长相同的积木会相邻。如果我们简单地遍历i之前的所有积木当遇到边长相同的积木j时虽然side[j] side[i]不满足“大于”的条件不会被用于转移这本身是正确的。但是我们必须确保在状态转移时不会错误地使用边长相同但高度更高的积木的dp值来更新当前积木吗不会因为我们的转移条件明确要求side[j] side[i]。所以排序是安全且有益的。综上所述我们的核心算法步骤是读取所有积木的(高度, 边长)信息。将所有积木按照边长从大到小进行排序。如果边长相同理论上按任意顺序排都可以但有时为了处理方便可以按高度降序排但这不影响最终结果。初始化一个dp数组dp[i]表示以第i块积木排序后为塔顶时的最大塔高。初始时每块积木都可以单独成为一座塔所以dp[i]至少等于它自身的高度height[i]。双重循环计算dp值外层循环i从0到n-1遍历每一块积木。内层循环j从0到i-1遍历所有排在i前面的积木。如果side[j] side[i]则说明积木i可以放在积木j上面。我们尝试用dp[j] height[i]来更新dp[i]即dp[i] max(dp[i], dp[j] height[i])。计算完所有dp[i]后整个dp数组中的最大值就是我们所求的最高塔高。因为最高塔的塔顶一定是某一块积木而我们计算了以每一块积木为塔顶时的最高塔高。3. 代码实现与逐行解读理论分析之后我们进入实战环节。我将提供一份清晰、完整的Python代码并附上详细的注释解释每一关键步骤的意图和注意事项。def max_tower_height(): # 1. 读取输入数据 n int(input().strip()) # 积木块数 blocks [] for _ in range(n): h, s map(int, input().strip().split()) # h:高度, s:边长 blocks.append((h, s)) # 2. 根据边长从大到小排序。如果边长相同可以按高度降序排但不是必须。 # 这里使用降序排序这样“前面”的积木边长更大。 blocks.sort(keylambda x: x[1], reverseTrue) # 3. 初始化dp数组dp[i]表示以排序后第i块积木为塔顶时的最大高度 # 初始值就是它自身的高度因为最差情况就是它自己单独成塔 dp [block[0] for block in blocks] # 4. 动态规划核心双重循环 n len(blocks) max_height 0 # 用于记录全局最大高度 for i in range(n): # 对于第i块积木检查所有在它之前的积木j for j in range(i): # 关键条件前面积木的边长必须严格大于当前积木的边长 if blocks[j][1] blocks[i][1]: # 状态转移尝试将当前积木i放到积木j所在的塔上 # dp[j] blocks[i][0] 表示新塔的高度 # 用其更新dp[i]取最大值 dp[i] max(dp[i], dp[j] blocks[i][0]) # 更新全局最大高度 max_height max(max_height, dp[i]) # 5. 输出结果 print(max_height) # 调用函数 if __name__ __main__: max_tower_height()现在我们来逐段解读这段代码并分析一些容易出错的细节。第一部分输入处理n int(input().strip()) blocks [] for _ in range(n): h, s map(int, input().strip().split()) blocks.append((h, s))这部分是标准输入。题目通常第一行给出积木数量n随后n行每行给出高度h和边长s。我们用一个列表blocks来存储所有的(高度, 边长)元组。使用strip()是为了去除行首尾可能存在的空格或换行符避免转换错误。这是竞赛中处理输入的基本功务必养成习惯。第二部分排序blocks.sort(keylambda x: x[1], reverseTrue)这是算法的关键预处理步骤。sort方法的key参数指定了排序的依据lambda x: x[1]表示按照每个元组的第二个元素即边长进行排序。reverseTrue表示降序排列即边长大的在前小的在后。思考为什么按边长降序排因为我们的状态转移需要找side[j] side[i]的j。排序后对于任意i所有满足j i的积木其边长blocks[j][1]都大于等于blocks[i][1]。这样我们在内层循环j从0到i-1查找时只需要判断“严格大于”这个条件而不需要扫描整个数组。这虽然没有降低理论时间复杂度还是O(n²)但让代码逻辑更清晰并且所有候选的j都集中在i的前面符合直觉。第三部分DP数组初始化dp [block[0] for block in blocks]dp[i]的初始值设为其自身高度。这很好理解至少每一块积木自己都可以构成一座高度为h的塔。这个初始值是状态转移的起点。第四部分动态规划双重循环这是整个算法的核心也是最容易写错的部分。for i in range(n): for j in range(i): if blocks[j][1] blocks[i][1]: dp[i] max(dp[i], dp[j] blocks[i][0]) max_height max(max_height, dp[i])外层循环for i in range(n)依次计算以每块积木i作为塔顶时的最优解dp[i]。内层循环for j in range(i)对于当前的i遍历所有排在它前面的积木j。因为我们已经按边长降序排序所以j的边长至少不小于i的边长。条件判断if blocks[j][1] blocks[i][1]这是放置规则的体现。必须严格大于i才能放到j上面。这里为什么是而不是因为题目要求“严格小于”即side[i] side[j]等价于side[j] side[i]。状态转移dp[i] max(dp[i], dp[j] blocks[i][0])这是动态规划的精华。dp[j]代表以j为塔顶的最高塔高。如果i能放在j上面那么新的塔高就是dp[j]j及其下面所有积木的高度和加上i自身的高度blocks[i][0]。我们用这个可能的新值去更新dp[i]始终保留最大值。更新全局最大值在计算完每个dp[i]后立即用其更新max_height。也可以在所有dp计算完后再用max(dp)求得但这样边计算边更新更清晰。一个重要的边界情况如果所有积木的边长都相同怎么办此时排序后所有积木的边长相等。对于任意i和jj i条件blocks[j][1] blocks[i][1]永远不成立因为边长相等。因此内层循环的if语句永远不会执行所有的dp[i]都保持为其初始高度blocks[i][0]。最终max_height就是所有积木中高度的最大值。这符合逻辑因为边长都相同任何两块积木都不能叠放最高塔只能是单独一块最高的积木。4. 复杂度分析与算法优化探索我们实现的动态规划算法时间复杂度是O(n²)空间复杂度是O(n)用于存储dp数组和排序后的blocks列表。对于蓝桥杯省赛级别的题目n的范围通常在10³以内O(n²)的算法即百万次操作完全可以在1秒内完成是安全且高效的。但是如果我们追求极致或者题目数据范围扩大到10⁵O(n²)就无法承受了。那么有没有更优的解法呢答案是肯定的但这需要引入更高级的数据结构来优化内层循环的“查找”过程。我们回顾一下状态转移方程dp[i] height[i] max{ dp[j] }, 其中side[j] side[i]。对于每个i我们都需要在所有边长大于side[i]的积木j中找到dp[j]的最大值。这本质上是一个在某个键值范围内查询最大值的问题。我们可以这样思考如果我们把积木按照边长从大到小排序后随着i的增大side[i]在减小或不变。我们需要维护一个数据结构它能存储已经处理过的积木即j i的积木的某些信息。能快速给出所有边长大于当前side[i]的积木中dp值的最大值。一个经典的优化方法是使用树状数组或线段树。我们可以以“边长”作为索引需要离散化因为边长可能很大以“dp值”作为存储的数据。当我们处理到积木i时我们需要查询的是所有边长大于side[i]的区间内的最大dp值。由于我们按边长降序处理我们可以反过来按边长升序处理并查询边长小于side[i]的区间最大值因为side[j] side[i]等价于side[i] side[j]如果我们升序处理i那么j是之前处理的边长更小的积木我们需要的是side[j] side[i]且dp[j]最大这不对。所以还是降序处理方便。实际上更直观的方法是我们按边长降序处理积木。对于当前积木i所有边长大于它的积木j都已经被处理过了。我们需要的是这些j中dp值的最大值。如果我们用线段树维护以边长为下标、dp值为元素的数组那么“边长大于side[i]”对应的是一个前缀区间因为边长从大到小排序大的边长下标小。我们需要查询下标从0到k-1这个区间的最大值其中k是第一个边长小于等于side[i]的积木位置。这可以通过线段树的区间最值查询在O(log n)时间内完成。查询到最大值max_dp后我们计算dp[i] height[i] max_dp。然后我们需要将当前积木i的信息更新到数据结构中即更新边长side[i]对应的位置离散化后的下标的值为dp[i]注意这里是更新因为可能有多个边长相同的积木我们取dp值大的那个实际上对于相同的边长它们之间不能叠放但以它们各自为顶的塔高dp值是需要分别记录和查询的。更准确地说线段树维护的是对于每个边长值S所有边长等于S的积木中最大的dp值是多少因为当后续一个更小边长的积木i想要放在某个边长为S的积木上时它当然会选择dp值最大的那个。所以当我们处理一个边长为S、dp值为val的积木时我们去看线段树中S位置当前的值old_val如果val old_val则用val更新它。这样算法的总复杂度就降为了O(n log n)。这对于大数据量是至关重要的。不过在蓝桥杯本题的语境下O(n²)的解法已经足够拿到满分。理解O(n log n)的优化思路对于提升算法能力更有意义。这里我不展开实现但希望你能理解这个优化方向将动态规划中需要遍历查找最值的部分通过排序和数据结构线段树/树状数组优化为对数时间。这是解决一类“二维偏序”最值问题的常用技巧。5. 测试用例设计与调试心得再好的算法没有经过充分测试心里也没底。尤其是动态规划边界条件和状态转移很容易出错。下面我设计了几组测试用例覆盖了各种典型和极端情况并附上手动计算过程你可以用来验证自己代码的正确性。测试用例1基础情况输入 4 10 5 20 8 15 3 25 12手动分析积木列表为[(10,5), (20,8), (15,3), (25,12)]。排序后按边长降序[(25,12), (20,8), (10,5), (15,3)]。DP过程i0 (25,12): dp[0]25。i1 (20,8): 检查j0边长128dp[1]max(20, 2520)45。i2 (10,5): 检查j0(125), dp[2]max(10, 2510)35检查j1(85), dp[2]max(35, 4510)55。i3 (15,3): 检查j0(123), dp[3]max(15, 2515)40检查j1(83), dp[3]max(40, 4515)60检查j2(53), dp[3]max(60, 5515)70。最大dp值max(25,45,55,70)70。验证最高塔的搭法是 12(25) - 8(20) - 5(10) - 3(15)不对边长5的积木(高10)不能放在边长8的积木(高20)上因为58可以放。但这样塔是12(25) - 8(20) - 5(10) - 3(15)高度为2520101570。正确。预期输出70。测试用例2所有积木边长相同输入 3 5 10 8 10 3 10手动分析所有边长都是10任何两块都不能叠放。排序后顺序任意假设为[(5,10), (8,10), (3,10)]。DP过程对于所有i内层循环的if条件blocks[j][1] blocks[i][1]1010永远为假。所有dp[i]保持初始高度。最大dp值max(5,8,3)8。预期输出8。测试用例3高度降序但边长乱序输入 5 50 1 40 2 30 3 20 4 10 5手动分析高度从大到小边长从小到大。最优塔应该是能放下最多积木的塔。由于边长严格递增12345理论上所有积木都能叠放从下到上边长5-4-3-2-1。但注意我们的排序是按边长降序所以顺序会变。排序后按边长降序[(10,5), (20,4), (30,3), (40,2), (50,1)]。DP过程i0 (10,5): dp[0]10。i1 (20,4): j0, 54, dp[1]max(20, 1020)30。i2 (30,3): j0(53), dp[2]max(30,1030)40; j1(43), dp[2]max(40,3030)60。i3 (40,2): j0(52), dp[3]max(40,1040)50; j1(42), dp[3]max(50,3040)70; j2(32), dp[3]max(70,6040)100。i4 (50,1): j0(51), dp[4]max(50,1050)60; j1(41), dp[4]max(60,3050)80; j2(31), dp[4]max(80,6050)110; j3(21), dp[4]max(110,10050)150。最大dp值150。验证塔从下到上为 (10,5) (20,4) (30,3) (40,2) (50,1) 1020304050150。正确。预期输出150。测试用例4单块积木输入 1 100 50预期输出100。测试用例5无法叠放任何积木输入 3 5 1 5 1 5 1分析所有积木边长相同无法叠放。预期输出5单块最大高度。在编写和调试代码时我总结了以下几点心得先排序再DP这是解决此类问题非常关键的一步。排序能将看似混乱的放置条件转化为有序的、可递推的关系。明确状态定义dp[i]是“以i为顶”还是“以i为底”这决定了状态转移的方向。本题“以i为顶”更自然因为转移时我们找的是能放在它下面的积木。重视初始值dp[i]的初始值至少是其自身高度这是状态的起点不要设为0。循环顺序外层循环遍历i内层循环遍历jj i这是计算这类DP的典型顺序确保了当我们计算dp[i]时所有dp[j]j i都已经计算好了无后效性。条件判断的严格性和一字之差结果天壤之别。务必看清题目是“小于”还是“小于等于”。使用测试用例像上面那样设计小型、有代表性的测试用例手动模拟DP过程是调试和验证算法正确性最有效的方法。尤其是边界情况如n1全相等完全有序等。6. 常见错误与避坑指南在实际解题和辅导他人的过程中我发现了一些高频出现的错误。这里集中列出来并解释原因和正确的做法。错误1错误的状态定义与转移错误代码示例# 错误试图用dp[i]表示前i块积木能组成的最大高度 dp [0] * (n1) for i in range(1, n1): dp[i] dp[i-1] # 不放第i块 for j in range(i): if blocks[j][1] blocks[i-1][1]: dp[i] max(dp[i], dp[j] blocks[i-1][0])问题分析这种定义破坏了动态规划的无后效性。dp[i]表示“考虑前i块积木”但转移时dp[j]j i所代表的塔其塔顶积木是固定的吗不一定。当我们尝试把第i块积木放到某个以j结尾的塔上时我们需要知道那个塔的塔顶边长而dp[j]只记录了高度丢失了塔顶信息。因此我们的状态必须包含“以谁结尾”这个信息这正是我们采用dp[i]表示“以第i块积木为塔顶”的原因。正确做法状态必须与具体的积木绑定记录以该积木结尾时的最优解。错误2排序依据选择错误错误想法按高度从大到小排序优先使用高积木。问题分析正如我们第二节反例所证明的贪心高度不可行。排序的目的是为了方便状态转移而不是贪心选择。本题排序应依据边长因为放置规则只与边长有关。正确做法按边长降序排序。错误3忽略“严格小于”条件错误代码if blocks[j][1] blocks[i][1]:问题分析题目明确要求“顶部积木的边长必须严格小于底部积木的边长”。如果写成则允许边长相等时叠放会导致结果错误可能比正确答案大。正确做法使用严格大于号。错误4DP数组初始化为0错误代码dp [0] * n问题分析如果初始化为0那么对于一块无法放在任何其他积木上的积木i它的dp[i]在经过内层循环后可能仍然是0因为所有if条件都不成立max(0, ...)还是0。但实际上它自己可以构成一座塔高度至少为height[i]。正确做法dp[i]初始化为height[i]。错误5输出前未取全局最大值错误代码计算完dp后直接print(dp[n-1])或print(max(dp))但放在了错误的位置。问题分析最高塔不一定以最后一块积木为顶。dp数组的每一个元素都代表一种可能性必须取其中的最大值。正确做法在DP过程中维护一个max_height变量或在DP结束后计算max(dp)。错误6输入处理不当潜在问题未使用strip()处理输入行当输入行首尾有空格时int()转换会失败。正确做法养成使用input().strip().split()的习惯。避坑总结画图辅助对于不直观的DP问题在纸上画出示意图列出几块积木手动推导一下状态转移能极大降低思维难度。打印中间结果在调试时可以在内层循环结束后打印i和dp[i]的值与手动计算的结果对比快速定位错误。测试驱动先写好几组测试用例和预期输出再用代码去验证而不是写完代码才想测试。理解优于记忆不要死记硬背“这是最长上升子序列变种”。要理解其本质一个基于偏序关系边长严格小于的、求最大权重和高度和的问题。状态设计要能体现这个偏序关系。7. 举一反三同类问题与扩展思考“乐乐的积木塔”本质上是一个带权值的最长链问题这里的“链”由偏序关系“边长大于”定义权值是积木的高度。这类问题有很多变体掌握其核心思想可以解决一大类题目。变体1俄罗斯套娃问题你有若干个信封每个信封有宽度w和高度h。如果一个信封的宽度和高度都分别大于另一个信封那么小的信封可以放进大的里面。请问你最多能套多少层信封LeetCode 354这和我们的积木塔非常像只是从一维比较边长变成了二维比较宽和高。解题思路也是动态规划但排序需要技巧通常先按宽度升序排序如果宽度相同则按高度降序排序目的是防止宽度相同的信封被错误地套入。然后问题就转化为在高度序列上求最长严格递增子序列LIS。这比积木塔多了一维但核心的排序DP思想是一致的。变体2最大整除子集给你一个正整数数组找出其中最大的子集使得子集中任意两个元素都满足较大元素是较小元素的倍数。LeetCode 368这可以看作是一种特殊的偏序关系“整除”。我们可以先排序然后定义dp[i]为以nums[i]为最大元素的、满足条件的最长子集大小。状态转移则是对于每个i遍历j从0到i-1如果nums[i] % nums[j] 0则dp[i] max(dp[i], dp[j] 1)。最后再回溯找出具体子集。其动态规划的结构和“积木塔”如出一辙。变体3带时间窗口的任务调度有n个任务每个任务有开始时间s、结束时间e和收益p。你不能同时做两个任务但一个任务结束后可以立刻开始另一个。如何选择任务使得总收益最大这可以转化为如果任务A的结束时间小于等于任务B的开始时间则A可以在B之前做。我们将任务按结束时间排序定义dp[i]为考虑前i个任务以第i个任务结尾的最大收益。状态转移dp[i] max(dp[i-1], dp[j] p[i])其中j是最后一个结束时间小于等于任务i开始时间的任务可以用二分查找快速找到。这仍然是排序后基于偏序关系的动态规划。扩展思考如果允许旋转积木呢假设积木是长方体有长a、宽b、高h。放置时要求接触面的长和宽都必须分别大于上面积木接触面的长和宽。你可以选择以哪一面作为底面。这该怎么办 思路对于一块积木我们可以生成它的6种放置方式3个维度轮流作为高另外两个作为长和宽注意长宽可以交换但通常规定长宽以避免重复。这样我们就把问题转化为了一个三维的“套娃”问题可以使用类似俄罗斯套娃的解法但状态转移的条件更复杂需要长和宽都满足条件。通过解决“乐乐的积木塔”这道题我们不仅学会了一个具体的动态规划解法更重要的是掌握了分析问题、定义状态、设计转移、处理边界的这一套方法论。在面对新的最优化问题时不妨先问问自己问题的约束条件是什么它定义了怎样的偏序关系状态如何设计才能包含足够的信息且无后效性排序能否让问题变得更有序想清楚这些很多难题就有了突破口。