有n块积木,每块积木有体积vol和重量weight两个属性,用二元组(vol,
weight)表示。积木需要搭成竖直的塔状,上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。
样例:
有7个积木boxes:
[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木,从上到下分别为:
(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6。
题目来源:CRACKING THE CODING INTERVIEW 9.7
其实就是个最长递减子序列的题,先排序,朴素的办......
阅读全文