次の再帰があります。
if(a%2 == 0){
f([a1,a2,...,aN],a,N) = (a1 + aN)/2 + f([a1,a2,...,a(N-1)],a+1,N-1)/2 +
f([a2,...,aN],a+1,N-1)/2;
}
else{
f([a1,a2,...,aN],a,N) = f([a1,a2,...,a(N-1)],a+1,N-1)/2 +
f([a2,...,aN],a+1,N-1)/2;
}
規範事例：
f([a1,a2],a,2) = (a1+a2)/2;
明らかに、再帰的に実装するとスタック オーバーフローが発生します。この再帰の最適解を得るには、動的計画法をどのように利用すればよいですか?
[a1,a2,..,aN] は整数配列を表します。
N の制限は 2000 で、a1、a2、..、aN <=999 です。
これは宿題の問題のようにひどくにおいがします。講師または TA と会うことをお勧めします。これは、インタラクティブに学習するのに最適な種類のものだからです。この情報を使用する場合は、盗用を避けるために必ず引用してください。
まず、結果が値で線形であることを観察します[a0, a1, ... aN]。したがって、実際にはそれらの係数を追跡するだけで済みます。{b1, b2, ..., bN}表記上の目的で、 represente と書きましょうb1 * a1 + b2 * a2 + ... bN * aN。
次に、いくつかの再帰を手作業で計算します。
f([a1, a2], a, 2) = { 1/2, 1/2 }の基本ケースですN=2。
見てみましょうN=3：
f([a1, a2, a3], a, 3)偶数a= .{1/2, 0, 1/2} + { f([a1, a2], a+1, 2)/2, 0 } + { 0, f([a2, a3], a+1, 2)/2 } = { 1/2, 0, 1/2 } + { 1/4, 1/4, 0 } + { 0, 1/4, 1/4 } = { 3/4, 1/2, 3/4 }
f([a1, a2, a3], a, 3)a奇数 =の場合{ f([a1, a2], a+1, 2)/2, 0 } + { 0, f([a2, a3], a+1, 2)/2 } = { 1/2, 0, 1/2 } + { 1/4, 1/4, 0 } + { 0, 1/4, 1/4 } = { 1/4, 1/2, 1/4 }。
今N=4：
f([a1, a2, a3, a4], a, 4)偶数a= . は偶数な{ 1/2, 0, 0, 1/2 } + { f[a1, a2, a3], a+1, 3)/2, 0 } + { 0, f([a2, a3, a4], a+1, 3)/2 }のでは奇数なので、 の場合です。偶数= .aa+1F([], even, 3)f([a1, a2, a3, a4], a, 4)a{ 1/2, 0, 0, 1/2 } + { 1/8, 1/4, 1/8, 0 } + { 0, 1/8, 1/4, 1/8 } = { 5/8, 3/8, 3/8, 5/8 }
f([a1, a2, a3, a4], a, 4)a奇数 =の場合{ f[a1, a2, a3], even, 3)/2, 0 } + { 0, f([a2, a3, a4], even, 3)/2 } = { 3/8, 1/4, 3/8, 0 } + { 0, 3/8, 1/4, 3/8 } = { 3/8, 5/8, 5/8, 3/8 }。
これで、係数が偶数か奇数Nかのみに依存することがわかります。a
これは、動的計画法でNと ブール値の各組み合わせの係数を記憶するだけでよいことを意味します。の上限は 2000 であるためN、必要なエントリは 4000 だけで、それほど負担にはなりません。実際、再帰を放棄して、上記のように単純にテーブル全体を段階的に計算することもできます。
a,N 値のすべてのペアの回答を保存する必要があります
各 ai の係数をインクリメンタルな方法で計算できます。残りの半分には繰り返し要素が含まれるため、特定の n の係数の半分を計算する必要があると思います。したがって、各 n にはテーブルに n/2 の値が含まれます。このアプローチでは、実行時間が n^2 になります。これがさらに改善される可能性があることを知りません。