algorithm - 正の象限のポイントの最大重みシーケンスを見つける

Question

正の象限に重み付けされたポイントのシーケンスが与えられた場合、連続する各ポイントが前のポイントと原点によって形成される長方形に含まれるように、ポイントの最大ウェイト シーケンスを見つける必要があります。

この問題の DP アルゴリズムに興味があります。

Answer 1

この問題は、実際には最長増加サブシーケンスを求めています。これを解決するための O(N log N) アルゴリズムは、ウィキペディアのページで説明されています。

より簡単な O(N²) アルゴリズム

私はあなたが整数点を持っていると仮定しています。そうでない場合は、座標圧縮を使用してポイントを N x N グリッドに配置できます。

したがって、各数値がその座標に割り当てられた重みである 2 次元の数値配列 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²) スペース) か、一度に 1 行ずつ計算する (O(N) スペース)ことができます。どちらのアルゴリズムも O(N²) 時間を使用します。

ペンと紙を使ってこの再帰を計算してみて、どのように機能するかを確認できます。