動的計画法の概要：重複するサブ問題と最適な部分構造

序章

25の二乗を解くための質問があったとしましょう。この質問に初めて直面する場合は、手元または電卓を使用して解くことができます。 しかし、この質問を以前に見たことがあるか、以前に解決したことがある場合は、それを覚えておくことですぐに答えられる可能性があります。

これにより、覚えていれば次回はスキップできるという結論に達しました。 動的計画法は同様の概念で機能します。アイデアは、計算の結果を記憶し、必要に応じて将来それを使用することです。

動的計画法のこの単純な手順は、プログラマーが効率的なコードの戦いを征服するための強力な武器になります。

たとえば、複雑な質問があり、その質問をサブ問題に分割する解決策を常に考えていると仮定します。 しかし、サブ問題を複数回計算する状況で立ち往生する可能性があります。 そこでは、最適なソリューションのために動的計画法を使用します。

動的計画法には2つの概念があります。

1. 重複するサブ問題
2. 最適な下部構造

重複するサブ問題

重複するサブ問題の概念を理解する典型的な例は、フィボナッチ数列を印刷するプログラムです。

フィボナッチ数列の論理は、「フィボナッチ（n）=フィボナッチ（n-1）+フィボナッチ（n-2）」で与えられます。 また、この関数をシームレスに実行するには、fibonacci（0）= 0およびfibonacci（1）=1の基本ケースを使用した再帰的ソリューションを使用します。

4番目のフィボナッチ桁を印刷する必要があるとすると、再帰ツリーは次のようになります。

フィボナッチ（4）

/ \

フィボナッチ（3）+フィボナッチ（2）

/ \ / \

フィボナッチ（2）+フィボナッチ（1）フィボナッチ（1）+フィボナッチ（0）

/ \

フィボナッチ（1）+フィボナッチ（0）

fibonacci（0）から開始するため、fibonacci（4）はfibonacciシリーズの5桁目であることに注意してください。 上記の再帰ツリーでは、fibonacci（2）が2回繰り返されていることがわかります。 高さ4の再帰ツリーで重複が観察されました。ここで、膨大な数の再帰呼び出しがあると想像してください。その後、高さの大きい再帰ツリーが作成されます。 そして、重複するサブ問題として知られている、そのような重複した計算がたくさんあります。

この（i）集計、（ii）メモ化に対処する方法は2つあります。

それらの実装をウォークスルーして、それらを理解しましょう。

メモ化

メモ化方法を使用してフィボナッチ問題を解決するには、以下のようにします。

上記のコードでは、ログファイルの維持またはルックアップテーブルの維持を作成し、計算結果の値を保存しています。 計算されたすべての値を記憶しているので、必要に応じて将来それらを使用できます。これにより、計算の重複やサブ問題の重複を回避できます。

すべてのロジックは再帰的なソリューションに似ていますが、唯一の違いは、値をmainメソッドに返す前に、メモ配列にそれらを記録していることです。 このアルゴリズムの唯一の制約は、サイズO（n）の余分なスペースが必要なことですが、以前の再帰的ソリューションを最適化しています。

集計

この方法は、上記の解決策とは少し異なります。 メモ化は、同じ再帰的なソリューションに従います。 しかし、表では、反復的な解決策に従います。 これは、ボトムアップアプローチとも呼ばれます。 ボトムアップアプローチの実装を見てみましょう。

fibonacci（n）= fibonacci（n-1）+ fibonacci（n-2）であることがわかっているので、メモ化ではfibonacci（4）関数呼び出しから始めましたが、その値を計算していないことに気づきました。その値を計算して保存しました。

同様の状況は、fibonacci（3）、fibonacci（2）のようなさらに再帰的な呼び出しに直面します。 これで、再帰スタックで多くの再帰呼び出しが待機しますが、とにかく、重複するサブ問題の重複をスキップしています。

また、0からn番目の要素までのフィボナッチを繰り返し計算してから、n番目のフィボナッチ要素を返す方法もあります。 これは、上記のコードで実装したものです。 このコードにも同じスペース要件O（n）があります。

チェックアウト：フルスタック開発者になるためのスキル

最適な下部構造

この概念では、対応するサブ問題を最適に解決した場合にのみ、問題の最適な解決策を得ることができます。

そして、この概念の典型的な例は、グラフ内のノード間のトラバーサルを検討することです。

テランガーナからデリーまで複数のルーツがあると仮定しましょう。 そして、ナグプールとグワリエルを通過する最短ルートがある場合。 次に、ナグプールからデリーデリーへの最短ルートはグワリエルを通過する必要があります。 これで、問題をサブ問題に分割できます。サブ問題は、テランガーナからナグプール、ナグプールからグワリエル、グワリエルからデリーです。

そして、このプロパティの典型的な例は、両方の文字列で最も長い共通部分列です。 サブシーケンスはサブストリングとは異なります。 サブシーケンスでは、文字は元の文字列の結果である必要はありません。

したがって、アイデアは、そのサブ問題を最適に解決することによってそれを解決することです。 nを最長共通部分列の長さとします。

n = LCS（potato、tattoo）の場合、n = LCS（potat、tatto）+1（最後の文字が同じ場合）、それ以外の場合、n = maximum（LCS（potato、tatto）、LCS（potat、tattoo））。

上記のコードでは、集計方法を使用してロジックを実装し、両方の文字列に存在する最長共通部分列の長さを計算しました。

また読む：インドのフルスタック開発者給与

世界のトップ大学からオンラインでソフトウェア開発コースを学びましょう。 エグゼクティブPGプログラム、高度な証明書プログラム、または修士プログラムを取得して、キャリアを早急に進めましょう。

結論

効率的なコードの戦いを克服するための強力な手法の1つを使用することに気付いたので、他の問題に対して動的計画法を実装してみて、動的計画法を使用して質問をコーディングする能力を強化し始めます。

結論として、フルスタック開発者コースは、Web開発に関連するすべてを処理できる高度なスキルを持つ専門家です。 これらのフルスタック開発者のスキルは、フロントエンドおよびバックエンド開発者との違いです。