例を考えてみましょうA [14,9,13,4,6,12,11,10]。インデックスが設定されている{1,3,5}か{1,4,6}、まばらです。{1,2,5}1,2 が隣接しているため、スパースではありません。
重みは、すべてのスパース インデックスの合計によって行われます。たとえば、w(1,3,5) = 14 + 13 + 6 = 33
0 <= k =< n W(k) を A のプレフィックス A[1..k] に設定されたスパース インデックスの最大重みとする場合、どのように W(k) の再帰を作成できますか?
W(k)すべてのを計算する動的計画法の疑似コードを作成するにはどうすればよい0 <= k <= nですか? みんなありがとう。