动态规划解决积木塔问题：从最长上升子序列到最优塔高-开发者社区

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(边长50<55)和B(边长45<55)都可以放在它上面！我们可以先放A（高100），再放B（高80），塔高为90+100+80=270。显然，270远大于180。这个例子清晰地告诉我们，局部的最优选择（单块积木高度最高）无法保证全局结果最优。塔的高度是所有使用积木的高度之和，而能否放置一块积木，只取决于它的边长与它下面那块积木边长的相对大小关系。一个边长更大的积木作为塔基，可能为更多的高度可观的积木提供“入场券”。

既然贪心不行，我们就要考虑更系统的方法。一个自然的想法是搜索，比如深度优先搜索(DFS)，枚举所有可能的积木排列顺序。对于n块积木，理论上有n!种排列，但其中绝大部分会因为不满足边长约束而被剪枝。即便如此，当n较大时（比如n>20），搜索空间依然会爆炸，导致程序超时。竞赛题目的数据规模通常会卡掉指数级复杂度的算法。

那么，如何高效解决呢？这就要引入我们今天的主角——动态规划。动态规划的核心思想是“将大问题分解为小问题，并存储小问题的解以避免重复计算”。对于本题，一个关键的突破口是排序。

注意：动态规划的状态设计和转移方程是解题的灵魂，直接决定了算法的效率和正确性。

我们仔细审视规则：“顶部积木的边长必须严格小于底部积木的边长”。这意味着，如果我们把积木按照某个维度排序，可能会让问题变得更清晰。应该按什么排序呢？高度还是边长？让我们来分析一下。

如果我们按高度排序，似乎没什么帮助，因为放置规则只关心边长。如果我们按边长排序呢？假设我们将所有积木按照边长从大到小排序。那么，对于排序后的序列，当我们考虑第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较大时（比如n=1000）是完全可以接受的（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(key=lambda x: x[1], reverse=True) # 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(key=lambda x: x[1], reverse=True)

这是算法的关键预处理步骤。sort方法的key参数指定了排序的依据，lambda x: x[1]表示按照每个元组的第二个元素（即边长）进行排序。reverse=True表示降序排列，即边长大的在前，小的在后。

思考：为什么按边长降序排？因为我们的状态转移需要找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和j（j < 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过程：
- i=0 (25,12): dp[0]=25。
- i=1 (20,8): 检查j=0，边长12>8，dp[1]=max(20, 25+20)=45。
- i=2 (10,5): 检查j=0(12>5), dp[2]=max(10, 25+10)=35；检查j=1(8>5), dp[2]=max(35, 45+10)=55。
- i=3 (15,3): 检查j=0(12>3), dp[3]=max(15, 25+15)=40；检查j=1(8>3), dp[3]=max(40, 45+15)=60；检查j=2(5>3), dp[3]=max(60, 55+15)=70。
最大dp值：max(25,45,55,70)=70。
验证：最高塔的搭法是 12(25) <- 8(20) <- 5(10) <- 3(15)？不对，边长5的积木(高10)不能放在边长8的积木(高20)上，因为5<8，可以放。但这样塔是：12(25) -> 8(20) -> 5(10) -> 3(15)，高度为25+20+10+15=70。正确。
预期输出：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]（10>10）永远为假。所有dp[i]保持初始高度。
最大dp值：max(5,8,3)=8。
预期输出：8。

测试用例3：高度降序但边长乱序

输入： 5 50 1 40 2 30 3 20 4 10 5

手动分析：高度从大到小，边长从小到大。最优塔应该是能放下最多积木的塔。由于边长严格递增（1<2<3<4<5），理论上所有积木都能叠放（从下到上：边长5->4->3->2->1）。但注意我们的排序是按边长降序，所以顺序会变。
排序后（按边长降序）：[(10,5), (20,4), (30,3), (40,2), (50,1)]。
DP过程：
- i=0 (10,5): dp[0]=10。
- i=1 (20,4): j=0, 5>4, dp[1]=max(20, 10+20)=30。
- i=2 (30,3): j=0(5>3), dp[2]=max(30,10+30)=40; j=1(4>3), dp[2]=max(40,30+30)=60。
- i=3 (40,2): j=0(5>2), dp[3]=max(40,10+40)=50; j=1(4>2), dp[3]=max(50,30+40)=70; j=2(3>2), dp[3]=max(70,60+40)=100。
- i=4 (50,1): j=0(5>1), dp[4]=max(50,10+50)=60; j=1(4>1), dp[4]=max(60,30+50)=80; j=2(3>1), dp[4]=max(80,60+50)=110; j=3(2>1), dp[4]=max(110,100+50)=150。
最大dp值：150。验证：塔从下到上为 (10,5) + (20,4) + (30,3) + (40,2) + (50,1) = 10+20+30+40+50=150。正确。
预期输出：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，内层循环遍历j（j < i），这是计算这类DP的典型顺序，确保了当我们计算dp[i]时，所有dp[j]（j < i）都已经计算好了（无后效性）。
条件判断的严格性：>和>=一字之差，结果天壤之别。务必看清题目是“小于”还是“小于等于”。
使用测试用例：像上面那样设计小型、有代表性的测试用例，手动模拟DP过程，是调试和验证算法正确性最有效的方法。尤其是边界情况（如n=1，全相等，完全有序等）。

6. 常见错误与避坑指南

在实际解题和辅导他人的过程中，我发现了一些高频出现的错误。这里集中列出来，并解释原因和正确的做法。

错误1：错误的状态定义与转移

错误代码示例：

# 错误：试图用dp[i]表示前i块积木能组成的最大高度 dp = [0] * (n+1) for i in range(1, n+1): 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]:
问题分析：题目明确要求“顶部积木的边长必须严格小于底部积木的边长”。如果写成>=，则允许边长相等时叠放，会导致结果错误（可能比正确答案大）。
正确做法：使用严格大于号>。

错误4：DP数组初始化为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个维度轮流作为高，另外两个作为长和宽，注意长宽可以交换，但通常规定长>=宽以避免重复）。这样，我们就把问题转化为了一个三维的“套娃”问题，可以使用类似俄罗斯套娃的解法，但状态转移的条件更复杂（需要长和宽都满足条件）。

通过解决“乐乐的积木塔”这道题，我们不仅学会了一个具体的动态规划解法，更重要的是掌握了分析问题、定义状态、设计转移、处理边界的这一套方法论。在面对新的最优化问题时，不妨先问问自己：问题的约束条件是什么？它定义了怎样的偏序关系？状态如何设计才能包含足够的信息且无后效性？排序能否让问题变得更有序？想清楚这些，很多难题就有了突破口。