动态编程问题

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，它也会满足另一个，如果它更短，它就不是最长的。