最大ゲインで順にジャンプ - 動的プログラミング

Question

私たちはアイテム1、...、nのシーケンスを持ち、すべてのアイテムはスコア（i）を持っています。アイテムを選択した場合、i + 1、... i + rest（i）アイテムは選択できません。目標は合計スコアを最大にすることです。

これを動的プログラミングで解決できます。

最初の項目には2つのオプションがあります。またはそれを選択して残りの（1）+ 1項目に行くか、それを選択せず​​に2番目の項目に移動します。

再帰関数：

c[i] = max{ c[i - 1], c[i + rest(i) + 1] + score(i) } 

この再帰関数の問題点は、サブ問題は独立していないという意味のサブ問題の間のサイクルを作成することです。

私はたぶんソリューションは、アイテムiにつながるすべての項目を与え、その後、それらの間の最大のスコアを取る機能を持っているだろう

c[i] = max{ c[i - 1], c[i - itemThatWentToItem(i)] + score(i) } 

のようなものを持っていることが理想的であると思います。

もう1つのアイデアは、この問題をDAG内の最長パスに変更して、すべてのサブグラフに対して実行することです。

アイデア？

Answer 1

コメントに追加。

def C(i, n): 
    if i > n: 
    return 0 
    return max(C(i+1, n), C(i+rest(i)+1)+score(i)) 
print C(0,n) 

それは後ろから値を計算することが最善（最速）である：はい、それは、再帰でのようなものを実装することができます。 （注：配列は1からnまでインデックス付けされます）：

# initialize array with lot of zeros: length + max score(i) 
cs = [0] * (n+max(rest(i) for i in range(0,n)+1) 
for i in range(n, 0, -1): 
    cs[i] = max(cs[i+1], cs[i+rest(i)+1]+score(i)) 
print cs[1]