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

Question

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

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

Answer 1

这道题其实是求最长的递增子序列。 wikipedia page 中描述了用于解决此问题的 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))

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

您可以尝试使用笔和纸来计算这种递归，看看它是如何工作的。