小编Dar*_*ria的帖子

“马戏团塔”的算法

这是《破解编码面试》一书中的问题:

\n\n

马戏团正在设计一种塔式表演,由人们相互站立\xe2\x80\x99s\n肩膀组成。出于实用和美观的原因,每个人都必须比他或她下面的人矮且轻。给定马戏团中每个人的身高和体重,编写一个方法来计算这样一座塔中的最大可能人数。

\n\n

例子:

\n\n

输入:

\n\n
(ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) \n
Run Code Online (Sandbox Code Playgroud)\n\n

输出:

\n\n

最长的塔长 6,从上到下包括:

\n\n
(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)\n
Run Code Online (Sandbox Code Playgroud)\n\n

这是书上的解决方案:

\n\n

“当我们剔除这个问题的所有废话时,我们就能明白问题实际上是以下这样的。

\n\n

我们有一个成对的项目列表。找到最长的序列,使得第一项和第二项都按非递减顺序排列。”

\n\n

我想出了这个例子:

\n\n
      {1,1} \n   {3,3} {7,2}\n{6,4} {9,9} {8,5}\n
Run Code Online (Sandbox Code Playgroud)\n\n

在这里,序列的值不是按非递减顺序排列的,但它仍然是一个有效的塔。而且我找不到一种方法将相同的物品组织到另一个塔中,该塔的物品按非递减顺序排列。我相信没有这样的办法。所以在我看来,这个解决方案是不正确的。

\n\n

我错过了什么吗?

\n\n

提前致谢。

\n

algorithm dynamic-programming

4
推荐指数
1
解决办法
3075
查看次数

标签 统计

algorithm ×1

dynamic-programming ×1