Jac*_*ale 6 sorting algorithm dynamic-programming
在Cracking the Coding Interview,第四版中,出现了这样一个问题:
一个马戏团正在设计一个由站在一个人的肩膀上的人组成的塔式例程出于实际和美学的原因,每个人必须比他或她下面的人更短更轻,考虑到马戏团中每个人的身高和体重,写一种方法来计算这种塔中最大可能的人数.
示例:输入(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找到包含增加高度和增加权重的最长序列为此,我们:
a)从序列的开头开始目前,max_sequence为空
b)如果对于下一个项目,高度和重量不大于前一个项目的高度和重量,我们将此项目标记为"不合格"
c)如果找到的序列的项目多于"最大序列",则变为"最大序列"
d)之后,从"不合适的项目"重复搜索,直到我们到达原始序列的末尾
我对其解决方案有一些疑问.
Q1
我相信这个解决方案是错误的.
例如
(3,2) (5,9) (6,7) (7,8)
显然,这(6,7)是一个不合适的项目,但怎么样(7,8)？根据解决方案,它并不是不合适的,因为它的h和w比较大(6,7),但是,它不能被考虑到序列中,因为(7,8)它不适合(5,9).
我对吗？
如果我是对的,修复是什么？
Q2
我相信即使有上述解决方案的解决方案,解决方案的风格至少会导致O(n^2),因为它需要一次又一次地迭代,根据步骤2-d.
那么有可能有一个O(nlogn)解决方案吗？
您可以使用动态规划来解决该问题。
\n\n按身高对剧团进行排序。为简单起见，假设所有高度 h_i 和重量 w_j 都是不同的。因此 h_i 是一个递增序列。
\n\n我们计算一个序列 T_i，其中 T_i 是一座塔，其中人物 i 位于最大尺寸的顶部。T_1 就是 {1}。我们可以从之前的 T_j \xe2\x80\x94 推导出后续的 T_k，找到可以承受 k 的重量（w_j < w_k）并让 k 站在上面的最大塔 T_j。
\n\n剧团中可能最大的塔就是 T_i 中最大的塔。
\n\n该算法需要 O(n**2) 时间，其中 n 是剧团的基数。
\n