一条线上有2*n个管脚，其中n个是输入管脚，n个是输出管脚。每个输入引脚必须连接到单个输出引脚，反之亦然，如下图所示：
连接线只能在上半平面上垂直和水平地制作，连接线不能重叠。
问题是，当连接所有管脚时，所有线路的最小长度是多少。
在上面的例子中，长度是31。
贪婪的方法使用堆栈，类似于匹配括号问题不是最优解。
最佳答案
如果你看1到8之间的最外线，它会将管脚分成两组。一个在2到7之间，另一个在9到10之间。
这些组中的每一个都对它的最大线高度有限制，而不需要通过外线延伸。第一个是2，第二个是5。
这就给出了一个函数lineLength(leftPin, rightPin, maxHeight)，它可以通过找到一个高度h和pini来获得它的值，从而使h <= maxHeight和pin[i]介于leftPin+1和rightPin之间，并且是相反类型的pin[leftPin]之间。
那么线的长度将rightPin-leftPin+2*h + lineLength(leftPin+1, i-1, h-1) + lineLength(i+1, rightPin-1, 5)
这个函数有O(n^3)可能的值，由于O(n^2)和h的迭代，使用memoization计算每个值需要i时间所以总时间是O(n^5)。
应该在最大高度上进行二值搜索来改善这一点。