集計とメモ化
1. 序章
このチュートリアルでは、動的計画法の2つの手法として、集計とメモ化について説明します。
2. 動的計画法
動的計画法（DP）は、最適化パラダイムであり、通常は多項式時間で、そのサブ問題を解決し、それらの解決策を組み合わせることによって、初期問題の最適な解決策を見つけます。 その際、DPはベルマンの最適性の原則を利用します。これは次のように述べています。
問題全体の最適解のサブ解は、対応するサブ問題の最適解です。
したがって、DPは最初に問題を分割して、問題全体の最適な解決策がそのサブ問題に対する最適な解決策の組み合わせになるようにします。 ただし、同じことがサブ問題にも当てはまります。それらの最適解は、サブ問題の最適解の組み合わせでもあります。 この分割は、ベースケースに到達するまで続きます。
したがって、 DPを使用して解決する各問題は、ベルマンの原理を尊重する再帰的な構造を持っています。問題の構造をトップダウンまたはボトムアップでトラバースすることにより、問題を解決できます。
3. 集計
集計は、DP問題を解決するためのボトムアップ方式です。基本ケースから開始し、直接のサブ問題が基本ケースである問題の最適な解決策を見つけます。 次に、1つ上のレベルに進み、以前に取得したソリューションを組み合わせて、より複雑な問題に対する最適なソリューションを構築します。
最終的に、集計は元の問題のサブ問題の解決策を組み合わせて、その最適な解決策を見つけます。
3.1. 例
グリッドがあるとしましょう。 セルにはコインが含まれています（）。 私たちの仕事は、セルからセルへのパスをたどることによって収集できるコインの最大量を見つけることです。 ボードを横切って移動する際に、セルからその右または下の隣に移動することができます。 セルに到達したら収集されたと見なします。
最適なパスが強調表示されたグリッドの例を次に示します。
3.2. 問題の再帰的構造
それがからへの最適なパスであり、セルを通過するとします。 次に、fromからへの部分は、2つのセル間の最適なパスを表します。 そうでない場合は、からへのより良いパスがあります。 したがって、との連結の方が優れているため、最適なパスにはなりません。これは矛盾します。
ここで、への最適なパスとその総歩留まりを決定したとしましょう。 以前の分析と問題の定義に基づいて、パススルーまたはを通過する必要があると結論付けます。 したがって、recursiveの定義は次のとおりです。
ただし、に当てはまるものは、すべてにも当てはまります。 基本ケースを説明すると、次の再帰的定義が得られます。
(1)
パスを再構築するには、補助マトリックスを使用できます。最適なパスが左から到達する場合（つまり、前のセルから1つのセルを右に移動する場合）、到達する場合は1つのセルを下に移動します。 ただし、物事を単純にするために（r）、パストレーシングを省略し、コンピューティングのみに焦点を当てます。
3.3. 集計アルゴリズム
ここで、再帰の方向を逆にします。 基本ケースから始めます。 そこから、st列と最初の行のセルへのパスの歩留まりを見つけます。 次に、2番目の列と行の値を計算します。
形をしたストライプを1つずつ処理すると、集計アルゴリズムが得られます。
このアルゴリズムの時間と空間の複雑さはです。
3.4. 集計の反再帰的な性質
まず、問題の再帰構造を特定して、再帰を正しく行うために多大な労力を費やします。 ただし、集計アルゴリズムは再帰的ではありません。 さらに、基本ケースから元の問題まで、逆方向に問題を解決します。 これが集計の最初の欠点です。 再帰式から集計アルゴリズムを取得するのは難しいかもしれません。
また、（ 1 ）のような漸化式は、解決すべき問題の自然な記述です。 したがって、問題の再帰的構造がそれほど明白ではない反復アルゴリズムよりも理解しやすいのです。
最後に、より単純な問題からより複雑な問題を体系的に構築する際に、集計アルゴリズムは、元の問題を解決するために必要ではないサブ問題の解決策を計算する場合があります。
4. メモ化
集計の効率を高め、再帰の優雅さと理解しやすさを維持する方法はありますか？はい、あります。これはメモ化と呼ばれます。
その背後にある考え方は次のとおりです。
このようにして、繰り返しの計算を回避し、時間の複雑さをさまざまなサブ問題の数に減らします。スペースの複雑さを犠牲にしてこれを行いますが、対応する集計アルゴリズムよりも多くのメモリを使用しません。
4.1. 例
グリッド問題のメモ化アルゴリズムは次のとおりです。
このアルゴリズムの時間と空間の複雑さはです。
4.2. 実行中のメモ化
メモ化の再帰ツリーの最初の3つのレベルを描画してみましょう。
アルゴリズムは、ルートの左側のサブツリーで計算しながら値を計算します。 後で、適切なサブツリーで計算するときに、最初から計算する必要はありません。 代わりに、メモリ内のすぐに利用可能な値を再利用します。
したがって、メモ化によって実行ツリーが効果的に削除されることがわかります。
4.3. メモ化の欠点
直感的で効率的ですが、メモ化が選択できない場合があります。
より微妙ですが、それでも関連する問題は、結果を保存するために使用するメモリに関連しています。 メモ化を機能させるには、-accessメモリ構造が必要です。ハッシュマップは、特にダブルハッシュを使用すると、最悪の場合のアクセス時間が一定になります。 ただし、（サブ）問題にはハッシュ関数が必要です。 コインの例では、高品質のハッシュを考案するのは簡単です。 ただし、問題は複雑である可能性があるため、ハッシュの設計は非常に難しい場合があります。
最後に、一部の作成者はメモ化をDPツールとは見なしていませんが、他の作成者は考慮しています。 それ自体は欠点ではありませんが、覚えておく価値があります。
5. 結論
この記事では、集計とメモ化について説明しました。 これらは、動的計画法（DP）のボトムアップおよびトップダウンのアプローチです。 後者がDP手法であるというコンセンサスはありませんが、両方の方法を使用して効率的なアルゴリズムを取得できます。
メモ化アルゴリズムは理解と実装が簡単ですが、スタックオーバーフロー（SO）エラーが発生する可能性があります。 集計アルゴリズムは反復的であるため、SOエラーはスローされませんが、一般に設計が困難です。
