私はこれらの言葉を読みました：
動的計画法を適用するために問題が持つ必要のある2つの重要な属性があります。それは、最適な部分構造と重複する部分問題です。重複しないサブ問題の最適なソリューションを組み合わせることで問題を解決できる場合、その戦略は「分割統治」と呼ばれます。これが、マージソートとクイックソートが動的計画問題として分類されない理由です。
私は3つの質問があります：
ここでのキーワードは「重複する部分問題」と「最適部分構造」です。クイックソートまたはマージソートを実行すると、配列が重複しない小さな部分に再帰的に分割されます。再帰の任意のレベルで、元の配列の同じ要素を2回操作することはありません。これは、以前の計算を再利用する機会がないことを意味します。一方、多くの問題は、重複するサブセットに対して同じ計算を実行することを含み、より大きな問題の最適解を計算するときに、サブ問題の最適解を再利用できるという有用な特性を持っています。
ダイクストラのアルゴリズムは、動的計画法の典型的な例です。以前の計算を再利用して、2つのノードAとZの間の最短経路を検出します。Aのすぐ隣がBとCであるとします。AからZへの最短経路は次のように見つけることができます。 AとBの間の距離を、BからZまでの計算された最短経路で合計します。CからZへの最短経路を見つけるためにも同様に行います。次に、AからZへの最短経路は、これら2つの経路のうち短い方になります。ここでの重要な洞察は、長さ3の最短パスを計算するときに、長さ2のパスの最短パス計算を再利用できることです。そうすることで、はるかに効率的なアルゴリズムが得られます。
動的計画法は、さまざまな種類の問題を解決するために使用できます。いくつかの例については、 http：//en.wikipedia.org/wiki/Dynamic_programming#Examples：_Computer_algorithmsを参照してください。
動的計画法を問題に適用するには、次のことが必要です。
私。サブ問題の最適な構造：
つまり、問題をより小さな単位に分割する場合、最適なソリューションを得るには、それらのより小さな単位もさらに小さな単位に分割する必要があります。たとえば、マージソートでは、数値の配列を2つのサブ配列に分割し、それらを並べ替えて結合すると、数値の配列を並べ替えることができます。これらの2つのサブ配列をソートしながら、前の文で行ったのと同じプロセスを繰り返します。したがって、そのサブ問題の最適な解決策を見つけると、最適な解決策（並べ替えられた配列）が得られます（サブ配列を並べ替えて結合します）。この要件は、マージソートで満たされます。また、サブ問題は、それらが最適な構造に従うために独立している必要があります。サブ問題のソリューションは互いのソリューションの影響を受けないため、これはマージソートによっても実現されます。例えば、
ii。重複するサブ問題：
これは、解を解く間、定式化するサブ問題が繰り返されるため、一度だけ解く必要があることを意味します。マージソートの場合、この要件が通常の場合に満たされることはめったにありません。2 1 3 4 9 4 2 1 3 1 9 4のような数値の配列は、マージソートのサブ問題を重複させるのに適した候補です。この場合、サブ問題sort（2 1 3）の解は、計算中に2回呼び出されるため、再利用するためにテーブルに格納できます。しかし、ご覧のとおり、ランダムな数の配列がこの種の繰り返しの工夫をする可能性は非常に低いです。したがって、マージソートなどのアルゴリズムにメモ化などの動的計画法を使用した場合にのみ非効率になります。