LIS | DP-21的变异

本文讨论了最长增长子序列问题的动态规划解法 这 post和一个O（nLogn）解决方案 这 邮递以下是标准的常见变化 LIS问题 .

1.建造桥梁： 考虑一个二维地图，一个水平河流通过它的中心。南岸有n座城市，x坐标为a（1）…a（n），北岸有n座城市，x坐标为b（1）…b（n）。你想用桥梁连接尽可能多的南北城市，这样就不会有两座桥梁交叉。连接城市时，只能将北岸的城市i连接到南岸的城市i。

8     1     4     3     5     2     6     7  <---- Cities on the other bank of river---->--------------------------------------------  <--------------- River--------------->--------------------------------------------1     2     3     4     5     6     7     8<------- Cities on one bank of river------->

资料来源： 动态规划实践问题 .该链接也很好地解释了问题的解决方案。 这个问题的解决方案已经公布 在这里 .

2.最大和递增子序列： 给定一个n个正整数的数组。编写一个程序来寻找给定数组的最大和子序列，以便子序列中的整数按递增顺序排序。例如，如果输入是{1,101,2,3,100,4,5}，那么输出应该是{1,2,3,100}。这个问题的解决方案已经公布 在这里 .

3.最长的链条 给你一对数字。在一对中，第一个数字比第二个数字小。假设你有两个集合（a，b）和（c，d），如果b 在这里 .

4. 箱子堆垛 你会得到一组n种类型的矩形三维长方体，其中第i个长方体有高度h（i）、宽度w（i）和深度D（i）（所有实数）。您希望创建一个尽可能高的长方体堆栈，但如果较低长方体的二维基座尺寸严格大于较高长方体的二维基座尺寸，则只能将一个长方体堆叠在另一个长方体的顶部。当然，你可以旋转一个长方体，这样任何一边都可以作为它的基础。还允许使用同一类型长方体的多个实例。 资料来源： 动态规划实践问题 .该链接也很好地解释了问题的解决方案。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。