算法问题：如何根据杂技演员体重与力量约束求解最高人塔高度

核心策略：贪心排序 + 动态规划 #

第一步：贪心排序 #

将所有杂技演员按照W[i] + S[i]的值从小到大排序。
该排序规则可通过交换论证证明合理性：假设有两名演员a、b，若将a放在b下方是更优的放置方式，可推导得出a.W + a.S < b.W + b.S的结论，按该规则排序可保证我们能得到最高的可行人塔。

第二步：动态规划求解最大高度 #

• 状态定义：设dp[h]表示搭建高度为h的人塔时，所需的最小总重量。总重量越小，后续越容易在底部加入新的演员抬高高度。
• 初始状态：dp[0] = 0（高度为0时总重量为0），其余dp值初始化为远大于1e9的无穷大值。
• 状态转移：遍历每一个排好序的演员，从当前已得到的最大可能高度倒序遍历到0：
  若dp[j] + W[i] <= S[i]，说明可以将当前演员放在高度为j的人塔底部，组成高度为j+1的人塔，此时更新dp[j+1] = min(dp[j+1], dp[j] + W[i])
• 结果提取：遍历dp数组，找到最大的h使得dp[h]不为无穷大，即为最高人塔高度。

复杂度说明 #

• 排序阶段时间复杂度为O(K log K)
• 动态规划阶段时间复杂度为O(K²)，K上限为5000时总运算量约2500万次，完全在可接受范围内。

内容的提问来源于stack exchange，提问作者Peter