我在准备期末考试时遇到了这个问题，尽管我看到了类似的问题，但我找不到递归公式。 我会感谢你的任何帮助！
问题是： 假设我们在平面上得到一组 L 的 n 条线段，其中端点 每个段位于单位圆 x 上 2 + y 2 = 1，所有 2n 个端点均为 不同。描述和分析算法以计算 L 的最大子集每对段相交
解决方案需要是动态规划方法中的算法(基于递归公式)
我假设问题("L的最大子集...")正在处理子集大小，而不是子集不能扩展。如果后者是正确的，那么问题就微不足道了，简单的贪婪算法是有效的。
现在回答你的问题。根据 Matt Timmermans 的提示(你能证明这一点吗？)，这可以被视为最长的常见子序列问题，除了我们不知道 2 个输入字符串是什么 = 2 个序列出现之间的分裂点在哪里。
最长的常见子序列问题可以在O(m*n)时间和线性记忆中求解。通过沿2n长度数组移动拆分点，您将创建 LCS 问题的2n实例，每个实例都可以在O(n^2)时间内解决，从而产生O(n^3)的总时间复杂度。
您的问题被称为圆图的最大集团问题(线段对应于图节点，线段相交对应于图边)，并且在 2010 年已被证明具有O(n^2*log(n))时间复杂度的解决方案。
请注意，在任意图的情况下，最大集团问题(决策版本)是NP-hard(确切地说是NP完全)。