algorithm - 给定一组点找到最大面积 k-gon

Question

我试图解决顶级编码器领域的练习题:http://topcoder.bgcoder.com/print.php?id=417

根据我的理解，问题的目的是找到一个最大面积的k边形，给定一组点D和k<=n，n是一个固定值。

设 D 的凸包 = C(D)

如果 n=3，我已经证明可以通过假设它的顶点是 C(D) 的子集来构造这样的三角形。所以很容易想出 k=3 的解决方案:https://stackoverflow.com/a/1621913/4126652

但是，对于 n>3，我不知道该怎么做。

以下是我的尝试:

令|C(D)| = l 即凸包是一个l边形，

如果 n > l 我很确定具有最大面积的 k 边形将是凸包本身，即 C(D)

如果 n < l 我很确定最大 k-gon 的顶点将是 C(D) 的一个子集，我无法证明 k>3，而且我无法想出一个算法解决即使这是一个正确的假设。

谁能帮我解决这个问题，我的方法正确吗？你能帮我继续吗？

Answer 1

在我绞尽脑汁几个小时后，我想出了解决办法。

这是一个动态规划问题:

设 dp[m][o][r] 表示最大面积 r-gon，起始顶点为 m，结束顶点为 o(顶点按循环顺序)。

则递推关系为:

dp[m][o][r] = max(dp[m][n][r-1] + area(m,n,o)), {所有 n 的最大值: m < n < o }

其中 area(m,n,o) 是由顶点 m、n 和 o 形成的三角形的面积