algorithm - 找到正象限中点的最大权重序列

Question

给定正象限中的加权点序列，我们必须找到点的最大权重序列，以便每个连续的点都包含在由前一个点和原点形成的矩形中。

我对这个问题的 DP 算法很感兴趣。

Answer 1

这个问题实际上是要求最长的递增子序列。维基百科页面上描述了用于解决此问题的 O(N log N) 算法。

更简单的 O(N²) 算法

我假设你有整数点。如果不这样做，您可以使用坐标压缩将您的点放置在 N x N 网格中。

因此，您有一个二维数字数组 W，其中每个数字都是分配给该坐标的权重。你现在有一个重复：

// T(w,h) = "Maximum weight of the point sequence in sub-grid (w,h)"
T(0,0) = W(0,0)
T(0,y) = W(0,y)+T(0,y-1)
T(x,0) = W(x,0)+T(x-1,0)
T(x,y) = W(x,y)+max(T(x-1,y),T(x,y-1))

您可以记住递归T（O(N²) 空间）或一次计算一行（O(N) 空间）。两种算法都将使用 O(N²) 时间。

您可以尝试使用笔和纸计算此重复次数，看看它是如何工作的。