皆さんの多くは聞いたことがあると思いますし、多くは、動的計画法のような特定の問題を解決するような方法に出くわしたことさえあると思います。 知らない人のために、Wikipediaの定義を次に示します。
動的プログラミングの考え方は、タスクをいくつかの独立したサブタスクに分割し、それぞれを解決してから、初期結果を計算することです。 サブタスクを解決するために、同じアルゴリズムが再帰的に適用されます。 この場合、各サブタスクについて、計算された回答が記憶され、あるステップでサブタスクが2回目に会った場合、計算は実行されません。
http://ru.wikipedia.org/wiki/Dynamic_programming
かなりわかりやすい説明ですが、例を見てみましょう。 一番頭に浮かぶのはフィボナッチ数だと思います。 いくつかの初期データが与えられます-A [1] = 1、A [2] = 1、その後、要素A [i] = A [i-1] + A [i-2]。 さらに、A [i]は状態と呼ばれることが多く、計算されたデータに関する特定の関係は遷移と呼ばれます。 この場合、A [i]からA [i-1]およびA [i-2]への2つの遷移があります。 遷移の数は、タスクによって異なる場合があります。
しかし、動的プログラミングは単に使用されるだけではありません。 つまり、問題の解決にかかる時間を非常に大幅に短縮できる場合があるため、大量の入力データでは非常に重要になることがあります。 そして、今年ゾーンスクールオリンピックで出会ったこのような問題の1つを示したいと思います。 文字通り、私はその状態を覚えていませんが、一般的な意味は次のとおりです。
サイズNxMと番号Kの数値Aの行列があります。その最初の行はA [1,1] .. A [1、M]です。 その後、最初の行の下の各要素に対して、値はKを法としてその上の三角形のすべての要素の合計として定義されます。この行列の最後の行を出力する必要がありますA [N、1] .. A [N、M]。 制限：1≤N、M≤2000; 2≤K≤10 9 。
したがって、任意の行の要素の意味を調べるには、その上のすべての行の要素の値を知る必要があります。 頭に浮かぶ最も簡単な解決策は、各要素がその上の三角形内のすべての要素を単純に取得および通過し、合計をカウントすることです。 はい、これは時間が重要でない場合、またはNとMの制限が小さい場合に実行できます。 このようなアルゴリズムは、次数O（N 4 ）の漸近線に対して機能します（N = Mの場合）。 つまり N = M = 100であっても、5〜10秒のオーダーで動作します（コンピューターによって異なります）。私はすでにN = M = 2000については黙っています。 そのため、このビジネスを何らかの形でスピードアップする必要があります。 これをやろう。 カウントする必要がある三角形があります。 そして、その上のすべての要素に対して事前に計算された三角形があります。 それでは、すでに計算された三角形を使用して新しい三角形を作成しましょう！ 写真を見ます：
つまり A [i、j]で始まる三角形を計算する必要がある場合、次の式で計算されます。
A [i、j] =（A [i-1、j] + 2 * A [i-1、j-1] + 2 * A [i-1、j + 1] -2 * A [i-2 、j]）mod K. （mod KはKを法とする）
三角形A [i-2、j]を引きます これは、2つの三角形A [i-1、j-1]とA [i-1、j + 1]の交差領域です。それ以外の場合は、2回カウントします。 ところで、いくつかの値に2を掛ける理由を自分で考えてください。
このタスクの一般的な考え方はこれです。 その解決策を自分で記述してみて（自分で見つけることをお勧めするニュアンスがいくつかあります）、さまざまなテストで通常の列挙アルゴリズムを使用してテストしてください。 不明な点がある場合は、連絡してください。私はこの問題のプロではなく、すべての問題を解決できないことを認めなければなりませんが、何かできることがあります;-)