algorithm - 动态规划题

Question

一个马戏团正在设计一个塔套路，其中的人站在彼此的塔顶上肩膀。出于实用和审美的原因，每个人都必须比他或她下面的人既矮又轻。给定马戏团中每个人的高度和体重，编写一个方法来计算最大可能人数在这样的塔里。

示例:
输入 (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
输出:最长的塔的长度为 6，从上到下包括:(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

有人给我建议如下:可以按如下方式完成:

1. 按权重递减的顺序对输入进行排序，并找到最长的高度递减序列。
2. 按高度降序对输入进行排序，找到最长的权重递减序列。

取 1 和 2 中的最大值。

我不明白为什么我们需要同时执行第 1 步和第 2 步。我们不能只执行第 1 步并找到答案吗？如果不是，请举例说明仅执行第 1 步不会给出答案？

Answer 1

1 和 2 的结果必须相同。它们中的一个不可能更短，因为在解决方案中，元素的高度和重量都在下降，所以如果它满足 1 或 2，它也会满足另一个，如果它更短，它就不会是最长的。